<!DOCTYPE html>



  


<html class="theme-next gemini use-motion" lang="zh-Hans">
<head>
  <meta charset="UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1"/>
<meta name="theme-color" content="#222">






  
  
  <link rel="stylesheet" media="all" href="/lib/Han/dist/han.min.css?v=3.3">




<meta http-equiv="Cache-Control" content="no-transform" />
<meta http-equiv="Cache-Control" content="no-siteapp" />
















  
  
  <link href="/lib/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css" />







<link href="/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css" />

<link href="/css/main.css?v=5.1.4" rel="stylesheet" type="text/css" />


  <link rel="apple-touch-icon" sizes="180x180" href="/images/favicon.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="32x32" href="/images/favicon.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="16x16" href="/images/favicon.png?v=5.1.4">


  <link rel="mask-icon" href="/images/favicon.png?v=5.1.4" color="#222">





  <meta name="keywords" content="操作系统," />





  <link rel="alternate" href="/atom.xml" title="平步青云win" type="application/atom+xml" />






<meta name="description" content="2019年11月份，操作系统复习笔记！">
<meta name="keywords" content="操作系统">
<meta property="og:type" content="article">
<meta property="og:title" content="操作系统学习笔记">
<meta property="og:url" content="https://zxpgo.github.io/2019/11/04/操作系统复习/index.html">
<meta property="og:site_name" content="平步青云win">
<meta property="og:description" content="2019年11月份，操作系统复习笔记！">
<meta property="og:locale" content="zh-Hans">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191008101917.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191008101947.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191008122549.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191010154343.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191010201257.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191010201451.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191010201908.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191010202010.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191010204858.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191010210941.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191010211248.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191010211640.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191010212716.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191015100429.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191015101108.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191015101641.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191015102417.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191015103304.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191015103839.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191015142733.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191015143410.png">
<meta property="og:image" content="c:/Users/zxp/AppData/Roaming/Typora/typora-user-images/1571123841590.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191015153912.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191016134903.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191016134829.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191016140647.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191016141828.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191016143324.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191017094735.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191017095633.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191017100653.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191017101515.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191017102411.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191017104251.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191018110535.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191018112628.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191018131141.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191018132355.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191018132516.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191018132928.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191018140853.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191018142452.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191018142904.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191018144537.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191018151740.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191019193157.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191019194339.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191019194944.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191019201032.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191019202252.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191020153401.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191020153914.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191020160641.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191027155527.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191027155721.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191027160131.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191027160539.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191027161532.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191027162225.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191028103419.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191028105419.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191028122644.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191101143543.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191101144026.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191101144757.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191101150559.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191101150917.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191101151718.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191101171904.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191104161206.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191104160210.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191106204603.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191106205334.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191106205811.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191106211051.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191106211638.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191106211822.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191106212416.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191107110330.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191107111005.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191107111808.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191107121302.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191108143447.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191110094103.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191110171506.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/safe.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/unsafe.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191111103036.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191111105616.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191111110214.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191111153514.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191112092911.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191112093431.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191112093704.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191112095442.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191112101137.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191112101335.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191112102213.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191112102405.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191112105956.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191112110015.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191112105646.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191112105812.png">
<meta property="og:updated_time" content="2019-11-25T14:36:26.692Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="操作系统学习笔记">
<meta name="twitter:description" content="2019年11月份，操作系统复习笔记！">
<meta name="twitter:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20191008101917.png">



<script type="text/javascript" id="hexo.configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/',
    scheme: 'Gemini',
    version: '5.1.4',
    sidebar: {"position":"right","display":"post","offset":10,"b2t":false,"scrollpercent":false,"onmobile":false},
    fancybox: true,
    tabs: true,
    motion: {"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},
    duoshuo: {
      userId: '0',
      author: '博主'
    },
    algolia: {
      applicationID: 'PAO8LM7QB1',
      apiKey: '',
      indexName: 'Blog',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
    }
  };
</script>



  <link rel="canonical" href="https://zxpgo.github.io/2019/11/04/操作系统复习/"/>





  <title>操作系统学习笔记 | 平步青云win</title>
  





  <script type="text/javascript">
    var _hmt = _hmt || [];
    (function() {
      var hm = document.createElement("script");
      hm.src = "https://hm.baidu.com/hm.js?7a4517a3ce6d7c50203655d056f01ac3";
      var s = document.getElementsByTagName("script")[0];
      s.parentNode.insertBefore(hm, s);
    })();
  </script>




</head>

<body itemscope itemtype="http://schema.org/WebPage" lang="zh-Hans">

  
  
    
  

  <div class="container sidebar-position-right page-post-detail">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-wrapper">
  <div class="site-meta ">
    

    <div class="custom-logo-site-title">
      <a href="/"  class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">平步青云win</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
      
        <h1 class="site-subtitle" itemprop="description"></h1>
      
  </div>

  <div class="site-nav-toggle">
    <button>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
    </button>
  </div>
</div>

<nav class="site-nav">
  

  
    <ul id="menu" class="menu">
      
        
        <li class="menu-item menu-item-home">
          <a href="/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-home"></i> <br />
            
            首页
          </a>
        </li>
      
        
        <li class="menu-item menu-item-about">
          <a href="/about/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-user"></i> <br />
            
            关于
          </a>
        </li>
      
        
        <li class="menu-item menu-item-tags">
          <a href="/tags/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-tags"></i> <br />
            
            标签
          </a>
        </li>
      
        
        <li class="menu-item menu-item-categories">
          <a href="/categories/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-th"></i> <br />
            
            分类
          </a>
        </li>
      
        
        <li class="menu-item menu-item-archives">
          <a href="/archives/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-archive"></i> <br />
            
            归档
          </a>
        </li>
      
        
        <li class="menu-item menu-item-随笔">
          <a href="/sui" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-question-circle"></i> <br />
            
            随笔
          </a>
        </li>
      

      
        <li class="menu-item menu-item-search">
          
            <a href="javascript:;" class="popup-trigger">
			
          
            
              <i class="menu-item-icon fa fa-search fa-fw"></i> <br />
            
            搜索
          </a>
        </li>
      
    </ul>
  

  
    <div class="site-search">
      
  <div class="popup search-popup local-search-popup">
  <div class="local-search-header clearfix">
    <span class="search-icon">
      <i class="fa fa-search"></i>
    </span>
    <span class="popup-btn-close">
      <i class="fa fa-times-circle"></i>
    </span>
    <div class="local-search-input-wrapper">
      <input autocomplete="off"
             placeholder="搜索..." spellcheck="false"
             type="text" id="local-search-input">
    </div>
  </div>
  <div id="local-search-result"></div>
</div>



    </div>
  
</nav>



 </div>
    </header>

    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          <div id="content" class="content">
            

  <div id="posts" class="posts-expand">
    

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="https://zxpgo.github.io/2019/11/04/操作系统复习/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="zxp">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/images/avatar.gif">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="平步青云win">
    </span>

    
      <header class="post-header">

        
        
          <h2 class="post-title" itemprop="name headline">操作系统学习笔记</h2>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2019-11-04T10:44:14+08:00">
                2019-11-04
              </time>
            

            

            
          </span>

          

          
            
          

          
          
             <span id="/2019/11/04/操作系统复习/" class="leancloud_visitors" data-flag-title="操作系统学习笔记">
               <span class="post-meta-divider">|</span>
               <span class="post-meta-item-icon">
                 <i class="fa fa-eye"></i>
               </span>
               
                 <span class="post-meta-item-text">阅读次数&#58;</span>
               
                 <span class="leancloud-visitors-count"></span>
             </span>
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body han-init-context" itemprop="articleBody">

      
      

      
        <p>2019年11月份，操作系统复习笔记！<a id="more"></a></p>
<p>Linux、Windows、Android的界面属于外壳（Shell），而不是内核(Kernel)，Kernel是我们研究的重点，在Shell之下。</p>
<p>Kernel-操作系统内部组件，包括：</p>
<ul>
<li>CPU调度 </li>
<li>物理内存管理</li>
<li>虚拟内存管理</li>
<li>文件系统管理</li>
<li>中断处理与设备驱动</li>
</ul>
<p>OS Kernel的特征：</p>
<ul>
<li>并发：一个时间段内，多个程序同时运行（并行，在同一个时间点上，有多个程序同时运行，需要多核）</li>
<li>共享：“同时”访问，互斥共享</li>
<li>虚拟：将硬件虚拟化，比如CPU虚拟化为进程、磁盘虚拟化为文件系统、内存虚拟化为地址空间。利用多道程序设计技术，让每个用户都觉得有一个计算机专门为他服务。</li>
<li>异步：程序的执行不是一贯到底，而是走走停停，向前推进的速度不可预知。但只要运行环境相同，OS需要保证程序运行的结果也要相同。</li>
</ul>
<p>操作系统结构：</p>
<ul>
<li>微内核的设计，尽可能把内核功能移动用户空间<ul>
<li>只在操作系统内核放最基本的功能，比如中断处理、消息传递</li>
<li>而其他功能比如文件系统、网络协议栈都是放在外围，以进程(服务)的形式存在，进制之间通过内核的消息机制进行通讯。</li>
</ul>
</li>
<li>外核：主要在学术界有研究<ul>
<li>分为两层：一层主要面向硬件，来复制硬件的功能；另一层主要面向应用，针对不同的应用有不同的Library Operating system</li>
<li>这样可以提高并发的效率，并且可以针对不同的应用设计Lib OS可以提高应用的运行效率</li>
</ul>
</li>
<li>VMM(虚拟机监视器)：操作系统之下是VMM，VMM之下是硬件，VMM之上是多个虚拟计算机。</li>
</ul>
<h2 id="操作系统启动"><a href="#操作系统启动" class="headerlink" title="操作系统启动"></a>操作系统启动</h2><p>操作系统一开始存放在：DISK</p>
<p>BIOS: 基本I/O处理系统，功能让计算机系统检测各种外设</p>
<p>Bootloader：加载OS，放在硬盘的第一个主引导扇区，一个扇区512个字节</p>
<ul>
<li><p>BIOS开始从一个固定地址开始执行，完成POST(加电自检)、寻找显卡和执行BIOS，从硬盘中加载Bootloader。并将控制权将给Bootloader。</p>
</li>
<li><p>然后Bootloader从硬盘找到操作系统的起始扇区以及操作系统的长度，将磁盘中的这个区域加载到内存中，即加载OS，并将控制权交给OS。</p>
</li>
<li>从OS起始地址开始执行，完成一些操作。</li>
</ul>
<h2 id="中断、异常和系统调用"><a href="#中断、异常和系统调用" class="headerlink" title="中断、异常和系统调用"></a>中断、异常和系统调用</h2><p>操作系统与设备和程序交互</p>
<p>面向外设：中断和IO</p>
<p>面向应用程序：异常和系统调用</p>
<h3 id="定义"><a href="#定义" class="headerlink" title="定义"></a>定义</h3><p><strong>系统调用</strong>：应用程序主动向操作系统发出服务请求，System call</p>
<p><strong>异常</strong>：非法指令或其他坏的处理状态（如：内存出错） exception</p>
<p><strong>中断</strong>：来自不同的硬件设备的计时器和网络的中断 interupt</p>
<p>为什么不让应用程序直接访问硬件？</p>
<ul>
<li><p>在计算机运行中，内核是被信任的第三方</p>
</li>
<li><p>只有内核可以执行特权指令</p>
</li>
<li><p>为了方便应用程序，屏蔽底层的差异性</p>
</li>
</ul>
<p>三者区别：</p>
<ul>
<li>源头：<ul>
<li>中断：外设</li>
<li>异常：应用程序意想不到的行为，让操作系统应对意外事件的支持；比如应用程序执行除0操作，此时计算机系统无法正常工作</li>
<li>系统调用：应用程序请求操作提供服务</li>
</ul>
</li>
<li><p>处理时间</p>
<ul>
<li>中断：异步，不知道什么时候产生</li>
<li>异常：同步，执行某条指令时产生</li>
<li>系统调用：异步或同步，执行某条指令时产生，也可能是异步的，即发出请求，响应的时间是不确定的(异步)</li>
</ul>
</li>
<li><p>响应</p>
<ul>
<li>中断：持续，对用户应用程序透明的</li>
<li>异常：杀死或者重新执行意想不到的应用程序指令</li>
<li>系统调用：等待和持续</li>
</ul>
</li>
</ul>
<h3 id="中断"><a href="#中断" class="headerlink" title="中断"></a>中断</h3><p>硬件：设置中断表示</p>
<ul>
<li>将内部、外部事件设置中断标记</li>
<li>中断事件的ID</li>
</ul>
<p>软件：</p>
<ul>
<li>保存当前处理状态</li>
<li>中断服务程序处理</li>
<li>清楚中断标记</li>
<li>恢复之前保存的处理状态</li>
</ul>
<h3 id="异常"><a href="#异常" class="headerlink" title="异常"></a>异常</h3><p>异常编号</p>
<ul>
<li>保存现场</li>
<li>异常处理<ul>
<li>杀死产生了异常的程序</li>
<li>重新执行异常指令：操作系统服务不到位，比如内存不足，但是操作系统收到异常后，回收了足够的内存，就可以重新执行异常指令</li>
</ul>
</li>
<li>恢复现场</li>
</ul>
<h3 id="系统调用"><a href="#系统调用" class="headerlink" title="系统调用"></a>系统调用</h3><p>程序访问主要通过高层次的API接口，而不是直接进行系统调用。</p>
<ul>
<li>Win32 API用于Windows。</li>
<li>POSIX API用于POSIX-Based systems，包括UNIX、LINUX、Max OS </li>
<li>Java API 用于JAVA虚拟机(JVM)</li>
</ul>
<p>应用程序处于用户态，操作系统处于内核态。只有在内核态才能访问外设、执行特权指令。所以如果应用程序需要访问外设都需要通过操作系统进行处理，即通过系统调用，将系统调用的参数传递到内核态。</p>
<p>注意，应用程序中函数的调用一般只需要一个栈，而系统调用需要两个栈，即用户栈和内核栈，所以在系统调用时，需要进行栈的切换。</p>
<p>跨越操作系统边界的开销：</p>
<ul>
<li>在执行时间上的开销超过程序调用</li>
<li>开销：<ul>
<li>建立中断/异常/系统调用号与对应服务例程映射关系的初始化开销</li>
<li>建立内核堆栈</li>
<li>验证参数</li>
<li>内核态映射到用户态的地址空间，更新页面映射权限</li>
<li>内核态独立地址空间，TLB</li>
</ul>
</li>
</ul>
<h1 id="内存"><a href="#内存" class="headerlink" title="内存"></a>内存</h1><h2 id="计算机体系结构及内存分层体系"><a href="#计算机体系结构及内存分层体系" class="headerlink" title="计算机体系结构及内存分层体系"></a>计算机体系结构及内存分层体系</h2><h3 id="计算机体系结构-内存分层体系"><a href="#计算机体系结构-内存分层体系" class="headerlink" title="计算机体系结构/内存分层体系"></a>计算机体系结构/内存分层体系</h3><p>计算机体系结构：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191008101917.png" alt=""></p>
<p>内存层次结构：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191008101947.png" alt=""></p>
<p>CPU访问的指令所处的位置。</p>
<p>CPU可以访问CPU寄存器和cache，这两者都位于CPU内部，速度快，容量小，存放的指令优先。</p>
<p>主存主要用于存放操作系统本身和运行的代码。CPU速度相当快，在主存中可以存放多个程序，在主存中放不下的数据，可以存放到磁盘中。而且主存一停电数据就没了，需要永久保存的数据放到磁盘中。磁盘速度比主存慢很多，但容量大。</p>
<p>操作系统在内存管理上要完成的任务：</p>
<ul>
<li>抽象<ul>
<li>逻辑地址空间 ！= 物理地址空间</li>
</ul>
</li>
<li>保护(隔离)<ul>
<li>同时运行多个不同的应用程序，每个应用有一片独立的地址空间</li>
</ul>
</li>
<li>共享<ul>
<li>进程间可以使用共享内存进行交互和数据的传递</li>
</ul>
</li>
<li>虚拟<ul>
<li>内存不足时可以使用硬盘获得更多的地址空间</li>
</ul>
</li>
</ul>
<h3 id="地址空间和地址生成"><a href="#地址空间和地址生成" class="headerlink" title="地址空间和地址生成"></a>地址空间和地址生成</h3><p>物理地址空间：硬件支持的地址看嘛</p>
<p>逻辑地址空间：一个运行的程序所拥有的内存范围</p>
<p>两者之间怎么对应关系的？</p>
<h4 id="逻辑地址生成"><a href="#逻辑地址生成" class="headerlink" title="逻辑地址生成"></a>逻辑地址生成</h4><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line">A[C程序.c] --&gt; |编译| B[编译程序.s]</span><br><span class="line">B --&gt; |汇编| C[汇编程序.o]</span><br><span class="line">C --&gt; |链接| D[执行程序.exe]</span><br><span class="line">D --&gt; |加载| E[应有载入内存]</span><br></pre></td></tr></table></figure>
<p>各个步骤的作用：</p>
<ul>
<li>编译：C程序代码中，每个指针（变量名、函数名）就代表一个逻辑地址，但该地址对硬件而言不友好的，因此先经过编译，将代码转为语法树，通过符号来描述地址。</li>
<li>汇编：经过汇编，将上一步的语法树转为机器语言，使用一段相对连续的，从零开始的地址描述程序。更加接近底层硬件语言。</li>
<li>链接：一个大的程序，可能通过.o文件组成，所以通过链接，将多个从零开始描述的.o文件组合到一起，并且使之不发生内存冲突。由此组成成为一个.exe应用程序，但此时该程序还存放到硬盘上。</li>
<li>载入(程序重定位)：将上一步中，硬盘上的应用程序，通过一定的偏移量加载到内存中。此时的地址依然是逻辑地址。</li>
</ul>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191008122549.png" alt=""></p>
<p>逻辑地址到物理地址的过程：</p>
<ul>
<li><p>CPU中MMU(内存管理单元)根据逻辑地址请求指令的内容。</p>
</li>
<li><p>CPU中的MMU查询逻辑地址中的映射表是否存在对应的物理地址，注意MMU有一块区域存储映射表。</p>
</li>
<li>如果找到了对应的物理地址，CPU的控制器向主存发起请求对应物理地址的内容。如果没有找到，则会去内存中查找。</li>
<li>主存通过总线将指令的内容传给CPU，CPU执行指令。</li>
</ul>
<p>操作系统需要建立逻辑地址到物理地址的映射关系，存放在内存中，由CPU进行缓存，从而加快访问过程。</p>
<p>操作系统确保内存中的程序相互不干扰：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191010154343.png" alt=""></p>
<p>起始地址和长度，指出一段区域是程序可以访问的。超出这个范围就是不合法的。</p>
<p>如果CPU执行某条指令，根据映射关系，判断逻辑地址是否在可以访问的区域，如果满足就根据映射关系找到对应的物理地址，读取物理地址的数据。如果不满足，就会产生内存异常。这就是地址的安全检测</p>
<h3 id="连续内存分配"><a href="#连续内存分配" class="headerlink" title="连续内存分配"></a>连续内存分配</h3><p>内存的碎片问题：</p>
<p>空闲内存不能被利用</p>
<ul>
<li>外部碎片：在分配单元间的无法使用的内存</li>
<li>内部碎片：在分配单元中的未使用的内存</li>
</ul>
<p>简单的内存管理方法：</p>
<ul>
<li>当一个程序准许运行在内存时，分配一个连续的空间</li>
<li>分配一个连续的内存空间给运行的程序以访问数据</li>
</ul>
<h4 id="分配策略"><a href="#分配策略" class="headerlink" title="分配策略"></a>分配策略</h4><h5 id="首次适配"><a href="#首次适配" class="headerlink" title="首次适配"></a>首次适配</h5><p>如要分配N byte，在内存中查找第一个可用（&gt;=N）的空闲块，以满足最快分配。</p>
<p>为了分配n字节，使用第一次可用空闲块以致块的尺寸比n大。</p>
<p>需求：空闲块按照地址排序；分配需要寻找一个合适的分区</p>
<p>优势：实现简单； 适合大量分配小内存。<br>劣势：重分配慢； 易产生大量微小的外部碎片。</p>
<h5 id="最佳适配"><a href="#最佳适配" class="headerlink" title="最佳适配"></a>最佳适配</h5><p>如要分配N byte，在内存中查找第一个可用（&gt;=N）的且最小的空闲块，以满足最快分配。更大的利用小空间。</p>
<p>需求：1. 按照剩余空间大小排序； 2. 分配需要寻找 最 合适的空闲块； 3. 内存回收后，要将相邻块进行合并。<br>优势：实现简单； 适合大量分配小内存。<br>劣势：重分配慢； 易产生大量微小的外部碎片。</p>
<h5 id="最差适配"><a href="#最差适配" class="headerlink" title="最差适配"></a>最差适配</h5><p>如要分配N byte，在内存中查找第一个可用（&gt;=N）的且最大的空闲块，以满足最快分配。避免出现大量微小空间。</p>
<p>需求：1. 按照剩余空间大小排序（倒序排列）； 2. 分配需要寻找 最 合适的空闲块； 3. 内存回收后，要将相邻块进行合并。<br>优势：适合大量分配中等大小内存。<br>劣势：重分配慢； 易产生外部碎片； 会破坏大的空闲块，使更大的应用无法分配。</p>
<h3 id="压缩式碎片整理"><a href="#压缩式碎片整理" class="headerlink" title="压缩式碎片整理"></a>压缩式碎片整理</h3><p>将非运行时应用占用的内存移动到相邻的一处内存，以减少应用间的外部碎片</p>
<h3 id="交换式碎片整理"><a href="#交换式碎片整理" class="headerlink" title="交换式碎片整理"></a>交换式碎片整理</h3><p>利用虚拟内存(磁盘)，将非运行时应用占用的内存移动到虚拟内存，以使的运行时应用有更大的空闲空间使用。</p>
<h2 id="非连续内存分配"><a href="#非连续内存分配" class="headerlink" title="非连续内存分配"></a>非连续内存分配</h2><p>连续分配内存的缺点：</p>
<ul>
<li>分配给一个车程序的物理内存是连续的</li>
<li>内存利用率较低</li>
<li>有外碎片、内碎片的问题</li>
</ul>
<p>非连续分配的优点：</p>
<ul>
<li>一个程序的物理地址空间是非连续的</li>
<li>更好的内存利用和管理</li>
<li>允许共享代码与数据</li>
<li>支持动态加载和动态链接</li>
</ul>
<p>非连续分配缺点：</p>
<ul>
<li>如何建立虚拟地址和物理地址之间的转换<ul>
<li>软件方案</li>
<li>硬件方案</li>
</ul>
</li>
<li>两种硬件方案<ul>
<li>分段</li>
<li>分页</li>
</ul>
</li>
</ul>
<h3 id="分段"><a href="#分段" class="headerlink" title="分段"></a>分段</h3><h4 id="程序的分段地址空间"><a href="#程序的分段地址空间" class="headerlink" title="程序的分段地址空间"></a>程序的分段地址空间</h4><p>数据分段：栈段、堆段、共享段</p>
<p>分段：更好的分离和共享</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191010201257.png" alt=""></p>
<p>左侧是连续的逻辑地址，右侧是不连续的物理地址。中间需要一个映射来建立关系。</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191010201451.png" alt=""></p>
<h4 id="分段寻址方案"><a href="#分段寻址方案" class="headerlink" title="分段寻址方案"></a>分段寻址方案</h4><p>段访问机制</p>
<p>一个段：一个内存“块”</p>
<p>程序访问内存地址需要一个2维的二元组(s,addr):</p>
<ul>
<li>s：段号</li>
<li>addr：段内偏移</li>
</ul>
<p>实现寻址的有两种方案：段寄存器+地址寄存器，x86采用该方案；另一种单段地址实现方案</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191010201908.png" alt=""></p>
<p>段的硬件实现：</p>
<ul>
<li>首先，CPU执行程序P中的指令，这时候需要寻址，采用单地址实现方案，把一个逻辑地址分为两部分：段号和偏移。</li>
<li>根据段号找到段所在物理内存的起始地址，这时候需要段表来存放逻辑地址段号到物理地址的映射关系。</li>
<li>CPU比对偏移是否小于等于段的长度限制，如果大于，这抛出内存异常；否则将基地址加上偏移得到真实的物理地址。</li>
</ul>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191010202010.png" alt=""></p>
<p>段表包括两个信息：</p>
<ul>
<li>段的起始地址</li>
<li>段的长度限制</li>
</ul>
<p>段号决定了索引段表中的哪一项。段表由操作系统建立。</p>
<p>根据段号就可以确定逻辑地址在物理内存中的起始地址。</p>
<h3 id="分页"><a href="#分页" class="headerlink" title="分页"></a>分页</h3><h4 id="分页地址空间"><a href="#分页地址空间" class="headerlink" title="分页地址空间"></a>分页地址空间</h4><p>划分物理内存到固定大小的帧(frame)，大小是2的幂，例如512，4096，8192。</p>
<p>划分逻辑地址空间至相同大小的页，大小是2的幂，例如512，4096，8192。</p>
<p>建立方案转换逻辑地址为物理地址（pages to frames）:</p>
<ul>
<li>页表</li>
<li>MMU/TLB</li>
</ul>
<p><strong>页帧：</strong>物理内存被分割为大小相等的帧</p>
<p>一个内存物理地址是一个二元组(f,o):</p>
<ul>
<li>f : 页帧号（F位，共有2^F个帧）</li>
<li>o: 帧内偏移（S位，每帧有2^S字节），所以一帧的大小位2^S</li>
</ul>
<p>物理地址：2^S×f+o，（其中2^S×f是基地址，o是偏移）</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191010204858.png" alt=""></p>
<p>地址计算实例：</p>
<p>16bit的地址空间，9bit（512byte）大小的页帧。</p>
<p>物理地址：(3,6)，对应的实际物理地址位：2^9×3+6=512×3+6=1542</p>
<p>这里F=7，S=9，f=3，o=6</p>
<p><strong>页：</strong>一个程序的逻辑地址空间被划分位大小相等的页：</p>
<ul>
<li>页内偏移大小=帧内偏移大小</li>
<li>页号大小&lt;&gt;帧号大小</li>
</ul>
<p>一个逻辑地址是一个二元组(p,o):</p>
<ul>
<li>p页号（P位，2^P个页）</li>
<li>o页内偏移（S位，每页有2^S字节）</li>
</ul>
<p>虚拟地址：2^S×p+o</p>
<h4 id="页寻址方案"><a href="#页寻址方案" class="headerlink" title="页寻址方案"></a>页寻址方案</h4><p>程序运行时，CPU去寻址，地址是一个逻辑地址，分为两部分：页号p和页内偏移o</p>
<p>根据页号查找页表，以页号为索引，可以得到帧号。在这个过程中，根据页表基址和页号来得到帧号。</p>
<p>根据帧号，结合页内偏移，得到了帧号和帧偏移，从而可以计算得到物理地址。</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191010210941.png" alt=""></p>
<p>页表由操作系统建立。</p>
<p>一般而言，逻辑地址空间大于物理地址空间，这个时候需要采用虚拟内存，后续会介绍。</p>
<p>逻辑地址空间是连续的，映射到物理地址空间，就不一定连续了，这有助于减少碎片。</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191010211248.png" alt=""></p>
<p>页机制有利于减少内存碎片。</p>
<h3 id="页表"><a href="#页表" class="headerlink" title="页表"></a>页表</h3><p>每个运行的程序都有一个页表：</p>
<ul>
<li>属于程序运行状态，会动态变化</li>
<li>PTBR：页表基址寄存器</li>
</ul>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191010211640.png" alt=""></p>
<p>页表项中的前三个bit有别的用途：</p>
<ul>
<li>页的读写情况</li>
<li>逻辑地址空间有没有对应到物理地址空间</li>
</ul>
<p>地址转换实例：</p>
<p>首先CPU读取逻辑地址，根据页号和页表基地址找到对应的页表项，比如页号是4，则对应页表中第二项，即Flags位为100，第二位为0，表示不存在该对应关系，即对应的逻辑地址没有对应的物理地址，抛出内存异常。</p>
<p>再来看(3,1023)，页号为3，即页表中第一项，即Flags为011，第二位为1，表示存在对应的映射关系。即可以得到该页号对应的帧号（00100=4），根据帧号加上帧偏移(等于页偏移1023)得到实际的物理地址，即(4,1023)，然后根据帧号到物理地址的关系计算得到实际物理地址。</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191010212716.png" alt=""></p>
<h4 id="分页机制的问题"><a href="#分页机制的问题" class="headerlink" title="分页机制的问题"></a>分页机制的问题</h4><ul>
<li>访问一个内存单元需要2次内存访问<ul>
<li>一次获取页表项</li>
<li>一次用于访问数据</li>
</ul>
</li>
<li>页表可能非常大<ul>
<li>64位机器如果每页1024字节，那么一个页表的大小会是多大？ 2^64/2^10=2^54，一般计算机内存无法存储一个页表。</li>
<li>计算机系统中可以跑多个应用程序，每个运行的程序都有一个自己的页表。</li>
</ul>
</li>
</ul>
<p>如何处理？</p>
<ul>
<li>缓存（Caching）</li>
<li>间接访问（Indirection）</li>
</ul>
<h4 id="Translation-Look-aside-Bufer-TLB"><a href="#Translation-Look-aside-Bufer-TLB" class="headerlink" title="Translation Look-aside Bufer(TLB)"></a>Translation Look-aside Bufer(TLB)</h4><ul>
<li>缓存近期访问的页帧转换表项<ul>
<li>TLB使用关联内存实现，具备快速访问性能</li>
<li>如果TLB命中，物理页号可以快速被获取</li>
<li>如果TLB未命中，对应的页表项被更新到TLB中</li>
</ul>
</li>
</ul>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191015100429.png" alt=""></p>
<p>TLB的容量有限，把经常访问的页表项映射关系存储到TLB。TLB缺失不会很大，一个页4K，访问4K次才会引起一次TLB缺失。</p>
<p>对于TLB未命中时，将页表项更新到TLB的实现方式有两种：一种是硬件实现，另一种是操作系统实现。x86采用的硬件实现。</p>
<h4 id="二级页表"><a href="#二级页表" class="headerlink" title="二级页表"></a>二级页表</h4><p>将page number分成两部分：p1,p2，即第一级页表的页号和第二级页表的页号。根据p1查找第一级页表项得到第二级页表的起始地址，然后根据p2和第二级页表的起始地址得到一个二级页表项，即一个起始地址，起始地址加上偏移o得到物理地址。</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191015101108.png" alt=""></p>
<h4 id="多级页表"><a href="#多级页表" class="headerlink" title="多级页表"></a>多级页表</h4><p>通过把页号分为k位，来实现多级间接页表。</p>
<p>建立页表“树”。</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191015101641.png" alt=""></p>
<p>多级页表通过时间换取空间，时间的开销可以通过TLB来缓解。</p>
<h4 id="反向页表"><a href="#反向页表" class="headerlink" title="反向页表"></a>反向页表</h4><p>大地址空间问题：</p>
<ul>
<li>有大地址空间（64-bits），前向映射页表变得繁琐</li>
<li>不是让页表与逻辑地址空间的大小相对应，而是让页表与物理地址空间的大小相应对</li>
</ul>
<h5 id="基于页寄存器的方案"><a href="#基于页寄存器的方案" class="headerlink" title="基于页寄存器的方案"></a>基于页寄存器的方案</h5><p>将物理地址的帧号作为页表的索引，然后第二项中存储逻辑地址的页号。这样页表的存储开销比较少，只跟物理地址空间有关，而与逻辑地址无关。</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191015102417.png" alt=""></p>
<p>每个帧和一个寄存器关联，寄存器内容包括：</p>
<ul>
<li>此帧是否被占用</li>
<li>对应的页号</li>
<li>保护位</li>
</ul>
<p>页寄存器的一个例子：</p>
<p>物理内存大小：4096×4096=4K×4K=16MB</p>
<p>页表大小：4096bytes = 4KB</p>
<p>页帧数：4097= 4K</p>
<p>页寄存器使用的空间：8 × 4096 = 32KB</p>
<p>页寄存器带来的额外开销：32K/32M = 0.2%</p>
<p>虚拟内容的大小：任意</p>
<p>现在的问题是，如何根据逻辑地址的页号来查找帧号？</p>
<h5 id="基于关联内存的方案"><a href="#基于关联内存的方案" class="headerlink" title="基于关联内存的方案"></a>基于关联内存的方案</h5><p>类似TLB，将页号设置为Value，将帧号设置为Key。</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191015103304.png" alt=""></p>
<p>开销太大，设计成本太大，硬件逻辑太复杂。还需要放入CPU中。</p>
<h5 id="基于哈希查找的方案"><a href="#基于哈希查找的方案" class="headerlink" title="基于哈希查找的方案"></a>基于哈希查找的方案</h5><p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191015103839.png" alt=""></p>
<p>为了提高效率，hash计算加入一个参数，即PID，当前进程ID。</p>
<p>根据PID和页号p通过hash计算得到帧号。</p>
<p>存在的问题：</p>
<ul>
<li>hash碰撞</li>
<li>还是需要将反向页表存储到内存中，存储开销大，还是需要TLB来缓解</li>
</ul>
<h2 id="虚拟内存"><a href="#虚拟内存" class="headerlink" title="虚拟内存"></a>虚拟内存</h2><h3 id="虚拟内存起因"><a href="#虚拟内存起因" class="headerlink" title="虚拟内存起因"></a>虚拟内存起因</h3><p>程序在运行时，进程发现内存不够用。程序的规模的增长速度远远大于存储容量的增长速度。让更多的程序跑在有限的内存中。</p>
<p>理想的存储器：更大、更快、更便宜的非易失性存储器</p>
<p>容量很少，速度更快的，放在CPU更近的地方，即寄存器。</p>
<p>Cache，缓存内存中的数据，尽量保证CPU访问数据更快。</p>
<p>由于内存远远无法满足，所以考虑是否用上磁盘。</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191015142733.png" alt=""></p>
<p>不常用的数据放到磁盘上去，虚拟出大内存：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191015143410.png" alt=""></p>
<p>对于内存不够用的情况，怎么办？</p>
<ul>
<li>如果是程序太大，超过了内存的容量，可以采用<strong>手动的覆盖（overlay）技术</strong>，只把需要的指令和数据保存在内存当中；</li>
<li>如果是程序太多，超过了内存的容量，可以采用<strong>自动的交换（swapping）技术</strong>，把暂时不能执行的程序送到外存中；</li>
<li>如果想要在有限容量的内存中，以更小的页粒度为单位转入更多更大的程序，可以采用<strong>自动的虚拟存储技术</strong>。</li>
</ul>
<h3 id="覆盖技术"><a href="#覆盖技术" class="headerlink" title="覆盖技术"></a>覆盖技术</h3><p>上世纪八九十年代。</p>
<p>目标：是在较小的可用内存中运行较大的程序。常用于多道程序系统，与分区存储管理配合使用。</p>
<p>原理：</p>
<ul>
<li>把个程序按照其自身逻辑结构，划分为若干个功能上相对独立的程序模块，那些不会同时执行的模块共享同一块内存区域，按时间先后来运行。<ul>
<li>必要部分（常用）的代码和数据常驻内存；</li>
<li>可选部分（不常用功能）在其他程序模块中实现，平时存放在外存中，在需要使用到时才转入内存；</li>
<li>不存在调用关系的模块不必同时转入到内存，从而可以相互覆盖，即这些模块共用一个分区。</li>
</ul>
</li>
</ul>
<p>下面就是一个例子：</p>
<p>内存总共就110K，但是程序大小为190K，内存无法加载整个程序，所以考虑使用覆盖技术。A首先调用B，然后将B导出到磁盘中，然后再调用C。C在调用E时，D和F不会存放在内存中。</p>
<p><img src="C:\Users\zxp\AppData\Roaming\Typora\typora-user-images\1571123841590.png" alt="1571123841590"></p>
<p>另一种覆盖方案（100K）：</p>
<ul>
<li>A占用一个分区20K</li>
<li>B、C、F占用一个分区50K</li>
<li>D、E占用一个分区30K</li>
</ul>
<p>覆盖技术 缺点：</p>
<ul>
<li>由程序员来把一个大的程序划分为若干个小的功能模块，并确定各个模块之前的覆盖关系，费时费力，增加了编程的复杂度；</li>
<li>覆盖模块从外存转入内存，实际上是以时间延长来换取空间节省。</li>
</ul>
<h3 id="交换技术"><a href="#交换技术" class="headerlink" title="交换技术"></a>交换技术</h3><p>目标：多道程序在内存中时，让正在运行的程序或需要运行的程序获得更多的内存资源。</p>
<p>方法：</p>
<ul>
<li>可将暂时不能运行的程序送到外存，从而获得空闲内存空间。</li>
<li>操作系统把一个进程的整个地址空间的内容保存到外存中（换出swap out），而将外存中的某个进程的地址空间读入内存中（换入swap in）。换入换出内容的大小为整个程序的地址空间。</li>
</ul>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191015153912.png" alt=""></p>
<p>交换技术实现中的几个问题：</p>
<ul>
<li>交换时机的确定：何时需要交换？只当内存空间不够或有不够的危险时换出；</li>
<li>交换区的大小：必须足够大以存放所有用户进程的所有内存映像拷贝；必须能对这些内存映像进行直接存取；</li>
<li>程序换入时的重定位：换出后再换入的内存位置一定要在原来的位置</li>
</ul>
<p>覆盖和交换的比较：</p>
<ul>
<li>覆盖只能发生在那些相互之间没有调用关系的程序模块之间，因此程序员必须给出程序内的各个模块之间的逻辑覆盖结构。</li>
<li>交换技术是以在内存中的程序大小为单位来进行的，它不需要程序员给出各个模块之间的逻辑覆盖结构。换言之，交换发生在内存中程序与管理程序或操作系统之间，而覆盖则发生在运行程序的内部。</li>
</ul>
<h3 id="虚存技术"><a href="#虚存技术" class="headerlink" title="虚存技术"></a>虚存技术</h3><p>在内存不足的情形下，可以采用覆盖技术和交换技术，但是两者存在缺点：</p>
<p>对于覆盖技术，需要程序员自己把整个程序划分位若干个小的功能模块，并确定各个模块之间的覆盖关系，增加了程序员的负担；</p>
<p>对于交换技术，以进程作为交换的单位，需要把进程的整个地址空间都换进换出，增加了处理器的开销。</p>
<p>四海之内的解决之道：虚拟内存管理技术——虚存技术。</p>
<p><strong>目标：</strong></p>
<ul>
<li>像覆盖技术那样，不是把程序的所有内容都放到内存中，因而能够运行比当前的空闲内存空间还要大的程序。但做得更好，由操作系统自动来加成，无须程序员干涉；</li>
<li>像交换技术那样，能够实现进程在内存与外存之间的交换，因而获得更多的空闲内存空间。但做得更好，只对进程的部分内容在内存和外存之间进行交换。</li>
</ul>
<p><strong>程序的局部性原理</strong>：指程序在执行过程中的一个较短时间内，所执行的指令地址和指令的操作数地址，分别局限于一定区域。这可以表现为：</p>
<ul>
<li>时间局部性：一条指令的一次执行和下次执行，一个数据的一次访问和下次访问都集中在一个较短时期内；</li>
<li>空间局部性：当前指令和邻近的几条指令，当前访问的数据和邻近的几个数据集中在一个较小区域内。</li>
</ul>
<p>程序的局部性原理表明，从理论上来说，虚拟存储技术是能够实现的，而且在实现了以后应该是能够取得一个满意的效果的。</p>
<p>程序的局部性好，程序执行效率高，得到高效的虚存管理。</p>
<p><strong>程序的编写方法对缺页率的影响：</strong></p>
<p>程序1是按照列来访问数组；程序2是按照行来访问数组的。</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191016134903.png" alt=""></p>
<p>在c语言中，数组是按照行来存储的。$a_{0,0}, …a_{0,1023}$占用一个页，而且是连续存储的。</p>
<p>对于程序1，首先产生中断从磁盘中读取第一行数据，访问$a_{0,0}$，正常访问，然后访问$a_{1,0}$位置上跟$a_{1,0}$相差一个页，不具备空间局部性和时间局部性，需要产生缺页中断才能从磁盘中读取$a_{1,0}$。访问整个数组需要产生1024×1024次缺页中断，所以开销比较大。</p>
<p>而对于程序2，首先产生中断从磁盘中读取第一行数据，访问$a_{0,0}$，然后访问$a_{0,1}$，两者在同一个页中，具有很好的空间局部性和时间局部性，在同一行数据访问时，都不会产生中断。一共只会产生1024次缺页中断。</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191016134829.png" alt=""></p>
<p><strong>基本概念：</strong></p>
<p>可以在页式和段式内存管理的基础上实现。</p>
<ul>
<li>在转入程序时，不必将其全部装入到内存，而只将当前需要执行的部分的代码和数据装入到内存中，就可让程序开始执行；</li>
<li>在程序执行过程中，如果需执行的指令或访问的数据尚未在内存（称缺页或缺段），则由处理器通过操作系统将相应的页面或段调入到内存，然后继续执行程序；</li>
<li>另一方面，操作系统将内存中暂时不使用的页面或段调出保存在外存上，从而腾出更多空闲空间存放将要装入的程序以及将要调入的页面或段。</li>
</ul>
<p>虚存技术基本特征：</p>
<ul>
<li>大的用户空间：通过把物理内存与外存相结合，提供给用户的虚拟内存空间通常大于实际的物理内存，即实现了这两者的分离。如32位的虚拟地址理论上可以访问4GB，而可能计算机上仅有256M的物理内存，但磁盘容量大于4GB。</li>
<li>部分交换：与交换技术相比较，虚拟存储的调入和调出是对部分虚拟地址空间进行的；</li>
<li>不连续性：物理内存分配的不连续，虚拟地址空间使用的不连续。</li>
</ul>
<h4 id="虚拟页式内存管理"><a href="#虚拟页式内存管理" class="headerlink" title="虚拟页式内存管理"></a>虚拟页式内存管理</h4><p>页式内存管理回顾：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191016140647.png" alt=""></p>
<p>大部分虚拟存储系统都采用虚拟页式管理技术，即在页式存储管理的基础上，增加<strong>请求调页和页面置换</strong>功能。</p>
<p>基本思路：</p>
<ul>
<li>当一个用户程序要调入内存运行时，不是将程序的所有页面都装入内存，而是只装入部分的页面，就可启动程序运行。</li>
<li>在运行的过程中，如果发现要运行的程序或要访问的数据不在内存，则向系统发出缺页中断请求，系统在处理这个中断时，将外存中相应的页面调入内存，使得该程序能够继续运行。</li>
</ul>
<p><strong>页表表项：</strong></p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191016141828.png" alt=""></p>
<ul>
<li>驻留位：表示该页是在内存还是外存。如果该位等于1，表示该页位于内存当中，即该页表项是有效的，可以使用；如果该位等于0，表示该页当前还在外存中，如果访问该页表项，将导致缺页中断；</li>
<li>保护位：表示允许对该页做何种类型的访问，如只读、可读写、可行等；</li>
<li>修改位：表明此页在内存中是否被修改过。当前系统回收该物理页面时，根据此位来决定是否把它的内容写回外存；如果该位为0，则该页没有被修改，跟硬盘中的数据一样，如果将该页换掉的话，直接释放就行，因为数据跟硬盘中的数据一样，下次需要时直接从硬盘读取就可以。</li>
<li>访问位：如果该页面被访问过，则设置此位。用于页面置换算法。置换页面时，尽量将没有访问的页面换出去，所以根据该位来判断，如果该位位0，表示没有被访问。</li>
</ul>
<p><strong>缺页中断处理过程：</strong></p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191016143324.png" alt=""></p>
<ul>
<li>如果在内存中由空闲的物理页面，则分配一个物理页帧f，然后转到第4步；否则转第2步；</li>
<li>采用某种页面置换算法，选择一个将被替换的物理页帧f，它所对应的逻辑页为q。如果该页在内存期间被修改过，则需要把它写回外存；</li>
<li>对q所对应的页表项进行修改，把驻留位改为0；</li>
<li>将需要访问的页p装入到物理页面f当中；</li>
<li>修改p所对应的页表项的内容，把驻留位改为1，把物理页帧号置为f；</li>
<li>重新运行被中断的指令。</li>
</ul>
<p><strong>后备存储（Backing Store）：</strong></p>
<p>在何出保存未被映射的页？</p>
<ul>
<li>能够简单地识别在二级存储器中的页</li>
<li>交换空间</li>
</ul>
<p>概念：</p>
<ul>
<li>一个虚拟地址空间的页面可以被映射到一个文件（在二级存储中）中的某个位置；</li>
<li>代码段：映射到可执行二进制文件；</li>
<li>动态加载的共享库程序段：映射到动态调用的库文件；</li>
<li>其他段：可能被映射到交换文件（swap file），程序在运行过程中，没有对应到数据文件、库文件、执行文件，动态产生的一些数据，这些数据占了很大的空间，且需要换出到硬盘中，操作系统会在硬盘中开出一个区域swap（换入换出分区），这个区域来放置没有文件对应的内存的内容。</li>
</ul>
<p>这四类组成了后背存储，或者二级存储。有了二级存储支持，使得虚存管理可以充分保证空间的有效性。</p>
<h4 id="虚拟内存性能"><a href="#虚拟内存性能" class="headerlink" title="虚拟内存性能"></a>虚拟内存性能</h4><p>为了便于理解分页的开销，使用有效存储器访问时间effective memory acces time(EAT):</p>
<p>EAT = 访存时间 × 页表命中几率 + page fault处理时间 × page fault 几率</p>
<p>例子：</p>
<p>访存时间： 10ns</p>
<p>磁盘访问时间： 5ms = 5 000 000ns</p>
<p>参数 p = page fault几率 （缺页的几率）</p>
<p>参数 q = dirty page 几率（页面被修改过的几率）</p>
<p>则：EAT = 10(1-p) + 5 000 000 p(1+q)</p>
<p>对于没有缺页时，访问时间位10ns；对于缺页时，需要磁盘访问，同时如果内存中的页面被修改过，还需要将该页的数据写回到磁盘中，需要增加一个次磁盘的访问，所以需要乘以1+q。</p>
<p>公司的右侧5 000 000远远大于10，但p足够小，就可以接近10ns。程序具有局部性特点，即意味着程序缺页的次数特别少，比如说在访问一个页是重复访问4K页，访问100万多次，然后才访问硬盘中的数据，这样缺页才产生一次。</p>
<h2 id="页面置换算法"><a href="#页面置换算法" class="headerlink" title="页面置换算法"></a>页面置换算法</h2><p>功能：当缺页中断发生，需要调入新的页面而内存已满时，选择内存当中哪个物理页面被置换。</p>
<p>目标：尽可能地减少页面的换进换出次数（即缺页中断的次数）。具体来说，把未来不再使用的或短期内较少使用的页面换出，通常只能在局部性原理指导下依据过去的统计数据来进行预测。</p>
<p>页面锁定：用于描述必须常驻内存的操作系统的关键部分或时间关键的应用进程。实现的方法是：在页表中添加锁定标志位。</p>
<p>记录一个进程对页面访问的一个轨迹：</p>
<p>举例：虚拟地址跟踪（页号，偏移）</p>
<p>(3,0), (1,9), (4,1), (2,1)，(5,3), (2,0), (1,9), (2,4), (3,1), (4,8)</p>
<p>生成页面轨迹：(考虑页面置换算法，可以把偏移去掉，只有当一个页不存在时，才会考虑页面置换算法)</p>
<p>3， 1，4，2，5，2，1，2，3，4（替换如c，a，d，b，e，b，a，b，c，d）</p>
<p>模拟一个页面置换的行为并且记录产生页缺失的数量：</p>
<p>更少的缺失，更好的性能。</p>
<h3 id="最优页面置换算法"><a href="#最优页面置换算法" class="headerlink" title="最优页面置换算法"></a>最优页面置换算法</h3><p><strong>基本思路</strong>：当一个缺页中断发生时，对于保存在内存当中的每一个逻辑页面，计算在它的下一次访问之前，还需要等待多长时间，从中选择等待时间最长的哪个，作为置换的页面。</p>
<p>这只是一种理想情况，在实际系统中是无法实现的，因为操作系统无从知道每一个页面要等待多长时间以后才会再次被访问。</p>
<p>该算法可用作其他算法的性能评价的一句（在一个模拟器上运行某个程序，并记录每一次的页面访问情况，在第二遍运行时即可使用最优算法）。</p>
<p>例子：</p>
<p>置换的页面是将来最长时间不需要的页面。</p>
<p>当前操作系统给程序分配了4个物理页帧，访问的页有5个。</p>
<p>在0时刻，物理页帧存储了abcd4个虚拟页，所以在前四次不会产生缺页中断。而在第5次访问时，e在物理页帧中没有对应，所以产生缺页中断，需要置换页。最长时间不需要访问的页是d，所以把d置换出去。</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191017094735.png" alt=""></p>
<h3 id="先进先出算法FIFO"><a href="#先进先出算法FIFO" class="headerlink" title="先进先出算法FIFO"></a>先进先出算法FIFO</h3><p><strong>基本思路：</strong>选择在内存中驻留时间最长的页面并淘汰之。具体来说，系统维护这一个链表，记录了所有位于内存当中的逻辑页面。从链表的排列顺序来看，链首页面的驻留时间最长，链尾页面的驻留时间最短。当发生一个缺页中断时，把链首页面淘汰出局，并把新的页面添加到链表的末尾。</p>
<p>性能较差，调出的页面有可能是经常要访问的页面，并且有Belady现象。FIFO算法很少单独使用。</p>
<p>Belady现象：当给一个程序分配更多的物理页时，采用FIFO时，给的物理页帧越多，产生缺失的次数更多。</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191017095633.png" alt=""></p>
<p>假设0时刻，4个页帧的顺序为a-&gt;b-&gt;c-&gt;d，所以在5时刻，产生缺页中断，置换的页面是a，并且将a从链表中删除，将e加入链表，得到4个页帧的顺序b-&gt;c-&gt;d-&gt;e。依此类推。6时刻没有缺页中断，7时刻产生缺页中断，将b置换出去。</p>
<h3 id="最近最久未使用算法（LRU）"><a href="#最近最久未使用算法（LRU）" class="headerlink" title="最近最久未使用算法（LRU）"></a>最近最久未使用算法（LRU）</h3><p>Least Recently Used</p>
<p><strong>基本思路：</strong>当一个缺页中断发生时，选择最久未使用的那个页面，并淘汰之。</p>
<p>它是对最优页面置换算法的一个近似，其依据是程序的局部性原理，即在最近一小段时间（最近几条执行）内，如果某些页面被频繁地访问，那么在将来的一小段时间内，它们还可能会再一次被频繁地访问。反过来说，如果在过去某些页面长时间未被访问，那么在将来它们还可能会长时间得不到访问。</p>
<p>例子：</p>
<p>置换的页面是最长时间没有被访问的。</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191017100653.png" alt=""></p>
<p>对于1-4时刻，都不会产生缺页中断，对于5时刻，由于页表中没有对应的项，所以产生缺页中断，置换的页面是c，因为c最近被访问的时刻是1，是未被使用时间最久的页面。</p>
<p>LRU算法需要记录各个页面使用时间的先后顺序，<strong>开销比较大</strong>。两种可能的实现方法是：</p>
<ul>
<li>系统维护一个页面链表，最近刚刚使用过的页面作为首节点，最久未使用的页面作为尾节点。每一次访问内存时，找到相应的页面，把它从链表中摘下来，再移动到链表之首。每次缺页中断发生时，淘汰链表末尾的页面。</li>
<li>设置一个活动页面栈，当访问某页时，将此页号压入栈顶，然后考察栈内是否有与此页面相同的页号，若有则抽出。当需要淘汰一个页面时，总是选择栈底的页面，它就是最久未使用的。</li>
</ul>
<p>保持一个最近使用页面的“栈”：</p>
<p>上面的例子使用栈实现的过程。</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191017101515.png" alt=""></p>
<h3 id="时钟页面置换算法"><a href="#时钟页面置换算法" class="headerlink" title="时钟页面置换算法"></a>时钟页面置换算法</h3><p>Clock页面置换算法，LRU的近似，对FIFO的一种改进。</p>
<p><strong>基本思路：</strong></p>
<ul>
<li>需要用到页表项当中的访问位，当一个页面被转入内存时，把该为初始化未0。然后如果这个页面被访问（读/写），则把该位置为1（置1的过程由硬件完成）。</li>
<li>把各个页面组织环形链表（类似钟表面），把指针指向最老的页面（最先进来）；</li>
<li>当发生一个缺页中断时，考察指针所指向的最老页面，若它的访问位为0，立即淘汰；若访问位为1，则把该位置为0，然后指针往下移动一格。如此下去，直到找到被淘汰的页面，然后把指针移动到它的下一格。</li>
</ul>
<p>维持一个环形页面链表保存在内存当中</p>
<ul>
<li>用一个时钟（或者使用/引用）位来标记一个页面是否经常被访问</li>
<li>当一个页面被使用时，这个位被设置位1</li>
</ul>
<p>时钟头扫遍页面寻找一个带有used bit = 0</p>
<ul>
<li>替换在一个周转内没有被使用过的页面</li>
</ul>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191017102411.png" alt=""></p>
<p>假设有5个物理页帧，有8个虚拟页。01347这五个虚拟页存放在物理内存中。第一个位表示是否存在物理内存中，第二个位表示是否被访问过。第三位是页帧号。</p>
<p>首先，指针指向上次访问的位置，程序正常运行，当遇到缺页中断时，需要将新的换入到物理内存中。从当前指针指向的页表项开始看，虚拟页0对应的页表项，第二位为1，表示最近刚被访问过，则将其置为0；并将指针指向下一个，同样第二位为1，将其置为0；再指向下一个页表项，第二位为0，将其置换出去，假设访问的是虚拟页6，则将虚拟页1对应的物理页5中的内容替换为虚拟页6对应的内容。</p>
<p>例子：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191017104251.png" alt=""></p>
<p>对于1-4时刻，将abcd访问一遍，所以将其used bit都置为了1。</p>
<p>5时刻，物理页没有空闲，而且e不在页表项中，所以产生中断进行页面置换，此时指针旋转一遍，将used bit全部置为0，回到a时，used bit为1，所以将a置换出去，同时e被访问，将used bit置为1，最后将指针指向下一项。</p>
<p>6时刻访问b，在页表项中，所以不会产生中断，只需将used bit置为1。</p>
<p>7时刻，a不在页表项中，所以指针寻找used bit为0的页表项，目前指针指向b，used bit为1，将其置为0，并指向下一项，此时为c的used bit为0，所以将其置换出去，并且将used bit置为1，最后将指针指向下一项。</p>
<p>8时刻，b在页表项中，直接访问即可，并将used bit设置为1。</p>
<p>。。。</p>
<p>产生了4次缺页中断，比LRU差一些，跟FIFO差不多。实际中，跟LRU接近的。</p>
<h3 id="二次机会"><a href="#二次机会" class="headerlink" title="二次机会"></a>二次机会</h3><p>used bit包括读和写，还有一个bit即dirty bit，即表示发生过写，dirty bit=1，由硬件完成。</p>
<p>如果某个页从硬盘读到内存，如果全部是读操作，这样内存中的内容和硬盘中的内容相同，发生置换时，直接将内存的内容释放即可，无需写回到硬盘中。如果发生过写操作，这样内存中的数据和硬盘中的数据不一致，发生置换时，需要写回到硬盘中。</p>
<p>dirty bit可用来clock算法，来提出更高效的clock算法，即二次机会法。将两个bit都用上，减少对硬盘的访问次数。</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191018110535.png" alt=""></p>
<p>只有当used bit和dirty bit都为0，才将其替换出去。</p>
<p>如果used bit为0，dirty bit为1，将dirty bit变为1；如果used bit为1，dirty bit为0，将used bit变为0;</p>
<p>如果used bit和dirty bit都为1，将used bit变为0。</p>
<p>被写过的页有更大的机会留在内存中，减少了对硬盘的访问次数。</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191018112628.png" alt=""></p>
<p>首先在0时刻，abcd4个虚拟页都被读过，但没有被写。经过1-4时刻，其中a和b被写过，所以a,b对应的标识位标称了11。</p>
<p>对于5时刻，虚拟页e在内存中不存在，所以需要置换，通过一遍遍历发现没有标识位为00，再一次遍历时，c的标识位变成了00，所以将c置换出去；并且e被读了，所以标识位标变成了10。</p>
<p>对于6时刻，内存中有虚拟页6，所以直接读取b。</p>
<p>对于时刻7，同样内存中有虚拟页a，于是写入a中，并将a的标识位置为11。</p>
<p>。。。</p>
<h3 id="最不常用算法LFU"><a href="#最不常用算法LFU" class="headerlink" title="最不常用算法LFU"></a>最不常用算法LFU</h3><p>Least Frequently Used</p>
<p><strong>基本思路：</strong>当一个缺页中断发生时，选择访问次数最少的那个页面，并淘汰之。</p>
<p>实现方法：对每个页面设置一个访问计数器，每当一个页面被访问时，该页面的访问计数器加1。在发生缺页中断时，淘汰计数值最小的那个页面。</p>
<p>LRU和LFU的区别：LRU考察的是多久未访问，时间越短越好；而LFU考察的访问次数或频度，访问次数越多越好。</p>
<p><strong>问题：</strong>一个页面在进程开始时使用得很多，但以后就不使用了，实现也费时费力。</p>
<p>解决办法：定期把次数寄存器右移一位。</p>
<p>练习题：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191018131141.png" alt=""></p>
<h3 id="Belady现象"><a href="#Belady现象" class="headerlink" title="Belady现象"></a>Belady现象</h3><p>Belady现象：在采用FIFO算法时，有时会出现分配的物理页面数增加，缺页率反而提高的异常现象。</p>
<p>Belady现象的原因：FIFO算法的置换特征与进程访问内存的动态特征是矛盾的，与置换算法的目标是不一致的（即替换较少使用的页面），因此，被它置换出去的页面并不一定是进程不会访问的。</p>
<h4 id="对于FIFO算法"><a href="#对于FIFO算法" class="headerlink" title="对于FIFO算法"></a>对于FIFO算法</h4><p>当分配3个物理页时：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191018132355.png" alt=""></p>
<p>如果分配4个物理页时：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191018132516.png" alt=""></p>
<p>从上面可以看出，3个物理页时产生9次缺页中断，而4个物理页时产生10次缺页中断。</p>
<h4 id="对于LRU"><a href="#对于LRU" class="headerlink" title="对于LRU"></a>对于LRU</h4><p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191018132928.png" alt=""></p>
<p>从上图可以看出，LRU算法在没有Belady现象。</p>
<p>LRU符合栈算法的特点。FIFO不满足栈算法的特点。</p>
<p>Clock算法和二次机会算法是否会产生Belady现象？</p>
<h3 id="LRU、FIFO、Clock算法比较"><a href="#LRU、FIFO、Clock算法比较" class="headerlink" title="LRU、FIFO、Clock算法比较"></a>LRU、FIFO、Clock算法比较</h3><p>LRU算法和FIFO本质上都是先进先出的思路，可以通过链表和栈来表示访问的次序。</p>
<ul>
<li>LRU除了驻留时间还考虑页面的最近访问时间来排序。所以需要在每一次页面访问的时候动态调整各个页面之间的先后顺序（有一个页面的最近访问时间变了）；</li>
<li>FIFO是针对页面进入内存的时间来进行排序的，这个时间是固定不变的，所以各个页面之间的先后顺序是固定的。如果一个页面在进入内存后没有被访问，那么它的最近访问就是它进入内存的时间。换句话说，如果内存当中的所有页面都未曾访问过，那么LRU算法就是退化的FIFO算法。</li>
</ul>
<p>Clock算法是对LRU算法的近似，利用一个bit来实现。</p>
<p>算法只是一个环节，除了算法本身，对于访问序列也有要求，需要具有局部性。如果序列不具备局部性，那么这些算法就没有区别了。</p>
<p>LRU算法性能较好，但系统开销大；FIFO算法开销较小，但可能会发生Belady现象。因此，折中的办法就是Clock算法，在每一次页面访问时，它不必动态地调整页面在链表中的顺序，而仅仅是做一个标记，然后等待发生缺页中断的时候，再把它移动到链表末尾。对于内存当中那些未被访问的页面，Clock算法的表现和LRU算法一样好；而对于那些曾经被访问过的页面，它不能像LRU算法那样，记住它们的准确位置。</p>
<h3 id="局部页面置换算法的问题、工作集模型"><a href="#局部页面置换算法的问题、工作集模型" class="headerlink" title="局部页面置换算法的问题、工作集模型"></a>局部页面置换算法的问题、工作集模型</h3><p>下面是一个FIFO页面置换算法的例子，第一次分配3个物理页，第二次分配4个物理页。</p>
<p>可以看出，第一次存在9次缺页，而对于第二次才1次缺页。物理页帧的大小对页面置换算法的效果产生很大的影响。</p>
<p>如果给一个程序分配一个固定的物理页帧，在某种程度上限制了程序它产生缺页的特点。程序在运行过程中有阶段性，在开始可能需要很多内存，中间一段时间需要很少内存，最后可能也需要很大的内存，是一个动态变化的过程。对物理页帧的需求是可变。前面对于物理页帧的分配都是固定的。</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191018140853.png" alt=""></p>
<p>但是一个操作系统里面可以跑多个程序，给每个程序分配固定的物理页帧，就限制了灵活性。根据程序的运行不同阶段，动态分配物理页帧，这就是全局页面置换算法考虑的问题。</p>
<h4 id="工作集模型"><a href="#工作集模型" class="headerlink" title="工作集模型"></a>工作集模型</h4><p>前面介绍的各种页面置换算法，都基于一个前提，即个程序的局部性原理。</p>
<p>如果局部性原理不成立，那么各种页面置换算法就没有区别，也没有意义。</p>
<p>如果局部性原理成立，那么如何来证明它的存在，如何来对它进行定量分析？这就是<strong>工作集模型</strong>。</p>
<p>工作集（working set）：一个进程当前正在使用的逻辑页面集合</p>
<p>可用一个二元函数$W(t,\Delta)$表示：</p>
<p>t是当前的执行时刻</p>
<p>$\Delta$称为工作集窗口（working-set window），即一个定长的页面访问的时间窗口</p>
<p>$W(t,\Delta)=$在当前时刻t之前的$\Delta$时间窗口当中的所有页面所组成的ejihe（随着t的变化，该集合也在不断地变化）；</p>
<p>$|W(t,\Delta)|$指工作集的大小，即页面数目。</p>
<p>一个例子：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191018142452.png" alt=""></p>
<p>可以看出$t_2$为起始时间的工作集局部性好，一直重复访问3和4。</p>
<p>工作集大小的变化：进程开始执行后，随着访问新页面逐步建立比较稳定的工作集。当内存访问的局部性区域的位置大致稳定时，工作集大小也大致稳定；局部性区域的位置改变，工作集快速扩张和收缩过渡到下一个稳定值。</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191018142904.png" alt=""></p>
<h4 id="常驻集"><a href="#常驻集" class="headerlink" title="常驻集"></a>常驻集</h4><p>常驻集：是指在当前时刻，进程实际驻留在内存当中的页面集合。</p>
<ul>
<li><p>工作集是进程在运行过程中固有的性质，而常驻集取决于系统分配给进程的物理页面数目，以及所采用的页面置换算法。</p>
</li>
<li><p>如果一个进程的整个工作集都在内存当中，即常驻集等于工作集，那么进程将很顺序地进行，而不会造成太多的缺页中断（直到工作集发生剧烈变动，从而过渡到另一个状态）。</p>
</li>
<li>当进程驻留集的大小到达某个数目之后，再给它分配更多的物理页面，缺页率不会明显下降。</li>
</ul>
<h2 id="两个全局置换算法"><a href="#两个全局置换算法" class="headerlink" title="两个全局置换算法"></a>两个全局置换算法</h2><h3 id="工作集页置换算法"><a href="#工作集页置换算法" class="headerlink" title="工作集页置换算法"></a>工作集页置换算法</h3><p>在之前$\tau$个内存访问的页引用是工作集，$\tau$被称为窗口大小。</p>
<p>随着程序的执行，只要页不属于工作集窗口，即使没有产生缺页，也会被丢弃。</p>
<p>如果产生缺页，我们要置换不在工作集中的页面。</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191018144537.png" alt=""></p>
<p>在0时刻，工作集中有dea，三个虚拟页，需要注意e的时刻t=-2，d的时刻t=-1。</p>
<p>在1时刻，c不在内存当中，产生缺页中断，将c写入内存当中，此时工作集变为：acde。</p>
<p>在2时刻，c在内存当中，直接读取即可，但是工作集变为dac，因为t=-2时刻距t=2超过了$\tau=4$，所以将e从工作集中删除，并且将该页从内存中删除。</p>
<p>在3时刻，d在内存当中，直接读取即可，但是工作集仍为acd。</p>
<p>….</p>
<p>这样可以确保物理内存中有足够多的页存在，从而可以给其他运行的程序足够多的内存，这样对于多个程序的层面。</p>
<h3 id="缺页率页面置换算法"><a href="#缺页率页面置换算法" class="headerlink" title="缺页率页面置换算法"></a>缺页率页面置换算法</h3><p><strong>可变分配策略：</strong>常驻集大小可变。例如每个进程在刚开始运行的时候，先根据程序大小给它分配一定数目的物理页面，然后再进程运行过程中，再动态地调整常驻集的大小。</p>
<ul>
<li>可采用<strong>全局页面置换</strong>的方式，当发生一个缺页中断时，被置换的页面可以是再其他进程当中，各个并发进程竞争地使用物理页面。</li>
<li>优缺点：性能较好，但增加了系统开销。</li>
<li>具体实现：可以使用缺页率算法（PFF, page fault frequency）来动态调整常驻集的大小。</li>
</ul>
<p><strong>缺页率：</strong></p>
<p>缺页次数 / 内存访问次数</p>
<p>影响缺页率的因素：</p>
<ul>
<li>页面置换算法</li>
<li>分配给进程的物理页数目</li>
<li>页面本身大小</li>
<li>程序的编写方法，局部性问题</li>
</ul>
<p>缺页率算法：</p>
<p>缺页率高，增加工作集来分配工作的物理页面；缺页率地，减少工作集来减少它的物理页数。力图使运行的每个程序的缺页率保持在一个合理的范围内。</p>
<p>算法：</p>
<p>保持追踪缺失发生概率：</p>
<p>​    当缺失发生时，从上次页缺失起计算这个时间记录这个时间，$t_{last}$是上次的页缺失的时间。</p>
<p>​    如果发生页缺失之间的时间是“大”的，之后减少工作集。</p>
<p>​     如果$t_{current} - t_{last} &gt; T $，之后从内存中移除所有在$[t_{current} - t_{last} ]$时间内没有被使用的物理页。</p>
<p>​     如果这个发生页缺失的时间“小”的，之后增加工作集。</p>
<p>​     如果$t_{current} - t_{last} &lt; T $，之后仅增加缺失页到工作集中。</p>
<p>一个例子：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191018151740.png" alt=""></p>
<p>在0时刻，物理内存中有ade三个虚拟页；</p>
<p>在1时刻，需要访问c，但是不在内存当中，所以产生缺页中断，但是这是第一次产生中断，所以我们不进行页的调整。</p>
<p>在2时刻，需要访问c，直接访问即可 ；</p>
<p>在3时刻，同样直接访问d即可；</p>
<p>在4时刻，由于b不在内存当中，所以产生缺页中断，将b读入到内存当中，由于当前产生缺页中断的时间距上次产生缺页中的时间等于3（大于2），所以需要将不在1和4时刻之间被使用过的页移除，即a,e。所以当前内存中有bcd三个页。</p>
<p>……</p>
<p>这两个算法是根据工作集和缺页率来动态调整内存中物理页的数量，这样可以确保整体上，经常访问的页驻留在内存当中。采用全局置换页算法优于局部置换页算法。</p>
<h2 id="抖动问题"><a href="#抖动问题" class="headerlink" title="抖动问题"></a>抖动问题</h2><p>对刚才的工作集和常驻集的讲解。</p>
<p>如果分配给一个进程的物理页面太少，不能包含整个的工作集，即常驻集被包含于工作集，那么进程将会造成很多的缺页蒜蓉，需要频繁地在内存与外存之间替换页面，从而使进程的运行速度变得很慢，我们把这种状态称为<strong>抖动</strong>。</p>
<p>产生抖动的原因：随着驻留在内存的进程数目增加，分配给每个进程的物理页数不断 减少，缺页率不断提升。所以操作系统要选择一个适当的进程数目和进程需要的帧数，一遍再并发水平和缺页率之间达到一个平衡。</p>
<h1 id="进程"><a href="#进程" class="headerlink" title="进程"></a>进程</h1><h2 id="进程描述-静态"><a href="#进程描述-静态" class="headerlink" title="进程描述(静态)"></a>进程描述(静态)</h2><h3 id="进程的定义"><a href="#进程的定义" class="headerlink" title="进程的定义"></a>进程的定义</h3><p>一个具有一定独立功能的个程序再一个数据集合上的一次动态执行过程。</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191019193157.png" alt=""></p>
<h3 id="进程的组成"><a href="#进程的组成" class="headerlink" title="进程的组成"></a>进程的组成</h3><ul>
<li><p>程序的代码</p>
</li>
<li><p>程序处理的数据</p>
</li>
<li><p>程序计数器中的值，指示下一条运行的指令</p>
</li>
<li><p>一组通用的寄存器的当前值、堆、栈</p>
</li>
<li><p>一组系统资源（如打开的文件）</p>
</li>
</ul>
<p>总之进程包含了正在运行的一个程序的所有状态信息。</p>
<p><strong>程序和进程的联系：</strong></p>
<ul>
<li>程序是产生进程的基础</li>
<li>程序的每次运行构成不同的进程</li>
<li>进程是程序功能的体现</li>
<li>通过多次执行，一个程序可以对应多个进程；通过调用关系，一个进程可包含多个程序。</li>
</ul>
<p>进程和程序是多对多的关系。</p>
<p><strong>程序和进程的区别：</strong></p>
<ul>
<li>进程是动态的，程序是静态；程序是有序代码的集合；进程是程序的执行，进程有用户态和内核态（有些操作需要操作系统去完成，比如读取文件，进程向操作系统发起请求，操作系统代表进程在内核中执行，此时进程处于内核态）。</li>
<li>进程是暂时的，程序是永久的：进程是一个状态变化的进程，程序是长久保存的。</li>
<li>进程与程序的组成不同：进程的组成包含程序、数据和进程控制块（即进程状态信息）。】</li>
</ul>
<p><strong>类比：</strong></p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191019194339.png" alt=""></p>
<h3 id="进程的特点"><a href="#进程的特点" class="headerlink" title="进程的特点"></a>进程的特点</h3><ul>
<li>动态性：可动态创建、结束进程，还可以切换</li>
<li>并发性：进程可以被独立调度并占用处理机运行；<ul>
<li>并发：多个程序交替执行，强调一段时间内，交替执行，看上去是同时执行；</li>
<li>并行：多个程序同时执行，强调同一时刻，同时执行，并行必须要求CPU是多核的。</li>
</ul>
</li>
<li>独立性：不同进程的工作不相互影响；<strong>页表</strong>是保证进程独立性的机制，每个进程只能访问自己页表对应的内存，在读取物理地址之前会有自检。</li>
<li>制约性：因访问共享数据/资源或进程间同步而产生制约。</li>
</ul>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191019194944.png" alt=""></p>
<p>(a):进程之间有切换，动态垂心</p>
<p>(b):进程之间的地址空间是独立的</p>
<p>(c):进程相互之间有时间调度的关系</p>
<p>怎么设计OS来实现进程管理机制呢？</p>
<p>程序 = 算法 + 数据结构</p>
<p>操作系统也是一个程序。</p>
<p>描述进程的数据结构：进程控制块（Process Control Block, PCB）。</p>
<p>操作系统为每个进程都维护了一个PCB，用来保存与该进程有关的各种状态信息。</p>
<h3 id="进程控制结构"><a href="#进程控制结构" class="headerlink" title="进程控制结构"></a>进程控制结构</h3><p>进程控制块：操作系统管理控制进程运行所用的信息集合。</p>
<p>操作系统用PCB来描述进程的基本情况以及运行变化的过程，PCB是进程存在的唯一标识。</p>
<p>进程的创建：为该进程生成一个PCB</p>
<p>进程的终止：回收它的PCB</p>
<p>进程的组织管理：通过堆PCB的组织管理来实现</p>
<p>PCB具体包含什么信息？如何组织的？进程的状态切换？</p>
<p><strong>PCB包含三大类信息：</strong></p>
<ul>
<li>进程标识信息：如本进程的标识，本进程的产生者标识（父进程标识），用户标识，那个程序在执行等等。</li>
<li>处理机状态信息保护区：保存进程的运行现场信息<ul>
<li>用户可见寄存器，用户程序可以使用的数据，地址等寄存器</li>
<li>控制和状态寄存器，如程序计数器（PC），程序状态字（PSW）</li>
<li>栈指针，过程调用/系统调用/中断处理和返回值需要用到它</li>
</ul>
</li>
<li>进程控制信息<ul>
<li>调度和状态信息：用户操作系统调度进程并占用处理机使用。</li>
<li>进程间通信信息：为支持进程间通信相关标识、信号等，这些信息存储在接收方的进程控制块中。</li>
<li>存储管理信息：包含由指向进程映像存储空间的数据结构。</li>
<li>进程所用资源：说明由进程打开、使用的系统资源，如打开的文件等。</li>
<li>有关数据结构连接信息：进程可以连接到一个进程队列中，或连接到相关的其他进程的PCB。比如B是A的子进程，C是B的子进程，可以通过一个链表来表示它们的关系。</li>
</ul>
</li>
</ul>
<p><strong>PCB的组织方式：</strong></p>
<ul>
<li><p>链表：同一状态的进程其PCB成一链表，多个状态对应多个不同的链表。进程是动态，存在删除、插入等等操作，采用链表效率更高。</p>
<p>各状态的进程形成不同的链表：就绪链表，阻塞链表</p>
</li>
<li><p>索引表：同一状态的进程归入一个index表（由index指向PCB），多个状态对应多个不同的index表。</p>
<p>各状态的进程形成不同的索性表：就绪索引表，阻塞索引表</p>
</li>
</ul>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191019201032.png" alt=""></p>
<p>目前更多采用基于链表的组织方式。如果进程个数比较固定，不会由频繁创建和删除的过程，采用索引表组织也是一种好办法。所以说，根据操作系统特点，是通用的操作系统，还是特殊的操作系统，可以采用不同的PCB组织方式。</p>
<h2 id="进程状态-动态"><a href="#进程状态-动态" class="headerlink" title="进程状态(动态)"></a>进程状态(动态)</h2><h3 id="进程的生命周期"><a href="#进程的生命周期" class="headerlink" title="进程的生命周期"></a>进程的生命周期</h3><ul>
<li><p>进程创建</p>
<p>进程创建的3个主要事件：</p>
<ul>
<li>系统初始化，第一个进程，NIT进程，这个进程再负责创建其他新的进程（下面两个）</li>
<li>用户请求创建一个新进程</li>
<li>正在运行的进程执行了一个创建进程的系统调用</li>
</ul>
<p>在内存中创建一个PCB，完成一系列初始化工作。</p>
</li>
<li><p>进程运行</p>
<p>内核选择一个就绪的进程，让它占用处理机并执行</p>
<p>如何选择？调度算法</p>
</li>
<li><p>进程等待</p>
<p>在以下情况，进程等待（阻塞）：</p>
<ul>
<li>请求并等待系统服务，无法马上完成，比如文件读写</li>
<li>启动某种操作，无法马上完成，比如和其他程序协同执行，等待其他执行完成</li>
<li>需要的数据没有到达</li>
</ul>
<p><strong>进程只能自己阻塞自己</strong>，因为只有进程自身才能知道何时需要等待某种事件的发生。</p>
</li>
<li><p>进程唤醒</p>
<p>唤醒进程的原因：</p>
<ul>
<li>被阻塞进程需要的资源可被满足</li>
<li>被阻塞进程等待的事件到达</li>
<li>将该进程的PCB插入到就绪队列</li>
</ul>
<p><strong>进程只能被别的进程或操作系统唤醒。</strong></p>
</li>
<li><p>进程结束</p>
<p>在以下四种情形下，进程结束：</p>
<ul>
<li>正常退出（自愿的）</li>
<li>错误退出（自愿的）</li>
<li>致命错误（强制性的）</li>
<li>被其他进程所杀（强制性的），比如管理进程，觉得该进程占用内存太多，将其杀死</li>
</ul>
</li>
</ul>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191019202252.png" alt=""></p>
<h3 id="进程状态变化模型"><a href="#进程状态变化模型" class="headerlink" title="进程状态变化模型"></a>进程状态变化模型</h3><p>进程的三种基本状态：</p>
<p>进程在生命结束前处于且仅处于三种基本状态之一。</p>
<p>不同系统设置的进程状态数目不同。</p>
<ul>
<li>运行状态：当一个进程正在处理机上运行时。</li>
<li>就绪状态：一个进程获得了除处理机之外的一切所需资源，一旦得到处理机即可运行。</li>
<li>等待状态（又称阻塞状态locked）：一个进程正在等待某一个事件而暂停运行。如等待某资源，等待输入/输出完成。</li>
</ul>
<p>进程其他的基本状态：</p>
<ul>
<li>创建状态：一个进程正在被创建，还没被转到就绪状态之前得状态</li>
<li>结束状态：一个进程正在从系统中消失时的状态，这是因为进程结束或由于其他原因所导致。</li>
</ul>
<p>状态变化图：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191020153401.png" alt=""></p>
<h2 id="进程挂起"><a href="#进程挂起" class="headerlink" title="进程挂起"></a>进程挂起</h2><p>进程在挂起状态时，意味着进程没有占用内存空间。处在挂起状态的进程映像在磁盘上。</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191020153914.png" alt=""></p>
<p>挂起状态：</p>
<ul>
<li>阻塞挂起状态：进程在外存并等待某事件的出现；</li>
<li>就绪挂起状态：进程在外存，但只要进入内存，即可运行。</li>
</ul>
<p>与挂起相关的状态转换：</p>
<p>挂起：把一个进程从内存转到外存，可能存在以下几个情况：</p>
<ul>
<li>阻塞态到阻塞挂起：没有进程处于就绪状态或就绪进程要求更多内存资源时，会进行这种转换，以提交新进程或运行就绪进程。</li>
<li>就绪态到就绪挂起：当有高优先级阻塞（系统认为很快会就绪的）进程和低优先就绪进程时，系统会选择挂起低优先级就行进程。这是因为高优先级阻塞态进程变成就绪态时，会在低优先级的就绪进程之前，会优先执行。</li>
<li>运行态到就绪挂起：对抢先式分时系统，当有高优先阻塞挂起进程因事件出现而进入就绪挂起时，系统可能会把运行进程转到就绪挂起状态。</li>
</ul>
<p>在外存时的状态转换：</p>
<ul>
<li>阻塞挂起到就绪挂起：当有阻塞挂起进程因相关事件出现时，系统会把阻塞挂起进程转换为就绪挂起进程。随着程序执行，阻塞挂起进程的资源得到了满足，应该变成就绪态，但是程序还在外存，所以还应该是就绪挂起，只是改变状态。</li>
</ul>
<p>与挂起相关的状态转换：</p>
<p>解挂/激活（Activate）：把一个进程从外存转到内存；可能有以下几种情况：</p>
<ul>
<li>就绪挂起到就绪：没有就绪进程或挂起就绪进程优先级高于就绪进程时，会进程该转换。</li>
<li>阻塞挂起到阻塞：当一个进程释放足够内存时，系统会把一个高优先级阻塞挂起进程转换为阻塞进程。</li>
</ul>
<p><strong>OS怎么通过PCB和定义的进程状态来管理PCB，帮助完成进程的调度过程？</strong></p>
<p>状态队列</p>
<ul>
<li><p>由操作系统来维护一组队列，用来表示系统当前所有进程的当前状态；</p>
</li>
<li><p>不同的状态分别用不同的队列表示；</p>
</li>
<li><p>每个进程的PCB都根据它的状态加入到相应的队列当中，当一个进程的状态发生变化时，它的PCB从一个状态队列脱离出来，加入到另一个队列。</p>
</li>
</ul>
<p>每个状态存在多个队列，用来对应不同的优先级。</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191020160641.png" alt=""></p>
<h2 id="线程"><a href="#线程" class="headerlink" title="线程"></a>线程</h2><h3 id="为什么需要线程？"><a href="#为什么需要线程？" class="headerlink" title="为什么需要线程？"></a>为什么需要线程？</h3><p>举例分析：MP3的实现，播放音乐包括三个过程：读取文件、解压文件、播放</p>
<p>单进程实现：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191027155527.png" alt=""></p>
<p>多进程实现：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191027155721.png" alt=""></p>
<p>怎么来解决这些问题？</p>
<p>提出一种新的实体，满足一下特性：</p>
<ul>
<li>实体之间可以并发地执行</li>
<li>实体之间共享相同的地址空间</li>
</ul>
<p>这就是线程。</p>
<h3 id="什么是线程？"><a href="#什么是线程？" class="headerlink" title="什么是线程？"></a>什么是线程？</h3><p>从资源角度来看，进程是用来管理地址：地址空间、打开的文件、网络</p>
<p>从运行的角度来看，代码在这个资源平台上的一条执行流程（线程）。</p>
<p>进程有自己的进程控制块（Thread control block）TCB。</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191027160131.png" alt=""></p>
<p>线程共享代码段和数据段，每个线程有自己的TCB，记录运行代码的逻辑。</p>
<p><strong>线程 = 进程 - 共享资源</strong></p>
<p>线程的优点：</p>
<ul>
<li>一个进程中可以同时存在多个线程；</li>
<li>各个线程之间可以并发地执行；</li>
<li>各个线程之间可以共享地址空间和文件等资源。</li>
</ul>
<p>缺点：</p>
<ul>
<li>一个线程崩溃，会导致所属进程的所有线程崩溃。</li>
</ul>
<p>浏览器通过进程来实现的，因为其需要可靠性，不能让一个网页崩溃，影响其他网页。</p>
<p>线程所需的资源：</p>
<p>多线程中每个线程都有各自的堆栈和寄存器。</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191027160539.png" alt=""></p>
<p>线程和进程的比较：</p>
<ul>
<li>进程是资源分配单位，线程是CPU调度的单位；</li>
<li>进程拥有一个完整的资源平台，而线程只独享必不可少的资源，如寄存器和栈；</li>
<li>线程同样具有就绪、阻塞和执行三种基本状态，同样具有状态之间的转换；</li>
<li>线程能减少并发执行的时间和空间开销：<ul>
<li>线程的创建时间比进程短</li>
<li>线程的终止时间比进程短</li>
<li>同一进程内的线程切换时间比进程短：线程切换不需要切换页表，而进程切换需要</li>
<li>由于同一进程的各线程共享内存和文件资源，可直接进行不通过内核的通信</li>
</ul>
</li>
</ul>
<h3 id="线程的实现方式"><a href="#线程的实现方式" class="headerlink" title="线程的实现方式"></a>线程的实现方式</h3><ul>
<li><p>用户线程：操作系统看不见的，由应用程序库来管理</p>
</li>
<li><p>内核线程：操作系统管理的</p>
</li>
</ul>
<p>用户线程与内核线程的对应关系：</p>
<ul>
<li>多对一</li>
<li>一对一</li>
<li>多对多</li>
</ul>
<h4 id="用户线程"><a href="#用户线程" class="headerlink" title="用户线程"></a>用户线程</h4><p>在用户看嘛实现的线程机制，它不依赖于操作系统的内核，有一组用户级的线程库函数来完成线程的管理，包括进程的创建、终止、同步和调度等。</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191027161532.png" alt=""></p>
<ul>
<li>由于用户线程的维护由相应进程来完成（通过线程库函数），不需要操作系统内核了解用户线程的存在，可用于不支持线程技术的多进程操作系统；</li>
<li>每个进程都需要它自己私有的线程控制块（TCB）列表，用来跟踪记录它的各个线程的状态信息（PC、栈指针、寄存器），TCB由线程库函数来维护；</li>
<li>用户线程的切换也是由线程库函数来完成的，无需用户态/内核态切换，所以速度特别快；</li>
<li>允许每个进程拥有自定义的线程调度算法。</li>
</ul>
<p>用户线程缺点：</p>
<ul>
<li>阻塞性的系统调用如何实现？如果一个线程发起系统调用而阻塞，则整个进程在等待；</li>
<li>当一个线程开始运行后，除非它主动交出CPU的使用权，否则它所在的进行当中的其他线程将无法运行；</li>
<li>由于时间片分配给进程，故于其他进程比，在多线程执行时，每个线程得到的时间片较少，执行会较慢。</li>
</ul>
<h4 id="内核线程"><a href="#内核线程" class="headerlink" title="内核线程"></a>内核线程</h4><p>windows操作系统采用内核线程。</p>
<p>内核线程是指在操作系统的内核当中实现的一种线程机制，有操作系统的内核来完成线程的创建、终止和管理。</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191027162225.png" alt=""></p>
<p>线程是CPU的调度单位，进程完成资源的管理。</p>
<ul>
<li>在持支内核线程的操作系统中，由内核来维护进程和线程的上下文信息（PCB和TCB）。</li>
<li>线程的创建、终止和切换都是通过系统调用/内核函数的方式来进行，由内核来完成，因此系统开销较大；</li>
<li>在一个进程中，如果某个内核线程发起系统调用而被阻塞，并不会影响其他内核线程的运行；</li>
<li>时间片分配给线程，多线程的进程获得更多的CPU时间；</li>
<li>Windows NT和Windows 2000/XP支持内核线程。</li>
</ul>
<h4 id="轻量级进程"><a href="#轻量级进程" class="headerlink" title="轻量级进程"></a>轻量级进程</h4><p>它是内核支持的用户线程，一个进程可有一个或多个轻量级进程，每个轻量级进程有一个单独的内核线程来支持。</p>
<p>LInux系统采用该种方式。</p>
<h2 id="上下文切换"><a href="#上下文切换" class="headerlink" title="上下文切换"></a>上下文切换</h2><p>进程的上下文切换。切换进程所用的寄存器，栈指针寄存器、程序寄存器等等。进程切换的将上下文写入进程控制块PCB中的某个位置。</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191028103419.png" alt=""></p>
<h2 id="创建进程"><a href="#创建进程" class="headerlink" title="创建进程"></a>创建进程</h2><p>fork() 创建一个继承的子进程</p>
<ul>
<li>复制父进程的所有变量和内存</li>
<li>复制父进程的所有CPU寄存器(有一个寄存器例外)</li>
</ul>
<p>fork()的返回值</p>
<ul>
<li>子进程的fork()返回0</li>
<li>父进程的fork()返回子进程标识符</li>
<li>fork() 返回值可方便后续使用，子进程可使用getpid()获取PID</li>
</ul>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">int</span> pid = fork()；		<span class="comment">// 创建子进程</span></span><br><span class="line"><span class="keyword">if</span>(pid == <span class="number">0</span>) &#123;			<span class="comment">// 子进程在这里继续</span></span><br><span class="line">     <span class="comment">// Do anything (unmap memory, close net connections…)</span></span><br><span class="line">	exec(“program”, argc, argv0, argv1, …);</span><br><span class="line">&#125;<span class="keyword">else</span> <span class="keyword">if</span>(pid &lt; <span class="number">0</span>)</span><br><span class="line">&#123;</span><br><span class="line">	<span class="built_in">printf</span>(<span class="string">"error!"</span>);</span><br><span class="line">&#125;</span><br><span class="line"><span class="keyword">else</span></span><br><span class="line">&#123;</span><br><span class="line">    <span class="built_in">printf</span>(<span class="string">"Whose your daddy?"</span>);</span><br><span class="line">    <span class="comment">//...</span></span><br><span class="line">    child_status = wait(pid); <span class="comment">//等待子进程结束</span></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191028105419.png" alt=""></p>
<p>exec()调用允许一个进程加载一个不同的程序并且在main开始执行。</p>
<p>执行的exec()时，程序本身的代码段和堆栈会被覆盖。</p>
<p>fork()的简单实现：</p>
<ul>
<li>对子进程分配内存</li>
<li>复制父进程的内存和CPU寄存器到子进程里</li>
<li>开销昂贵！！</li>
</ul>
<p>在99%的情况里，我们在调用fork()之后调用exec()：</p>
<ul>
<li>在fork()操作中内存复制是没有复制的</li>
<li>子进程将可能关闭打开的文件和连接</li>
<li>开销因此是高的</li>
</ul>
<p>vfork()</p>
<ul>
<li>一个创建进程的系统调用，不需要创建一个同样的内存映像</li>
<li>一些时候称为轻量级fork()</li>
<li>子进程应该几乎立即调用exec()</li>
</ul>
<p>现在不在使用vfork()技术，因为存在了<strong>Copy on Write(COW)</strong>技术。通过虚存管理，来实现的。即写的时候在复制。</p>
<p>并没有真实复制整个地址空间，而是仅仅复制地址空间的页表，指向同一块地址空间。当父进程或子进程对某一个地址单元进行写操作时，触发一个异常，使得父进程和子进程将触发异常的页复制成两份。如果只是只读，就不需要复制，因为使用同一块数据。不管执不执行exec，fork()还是创建一个子进程，只复制了页表，根据是否有写操作来进行复制。</p>
<h2 id="进程等待和终止"><a href="#进程等待和终止" class="headerlink" title="进程等待和终止"></a>进程等待和终止</h2><p>wait()系统调用是被父进程用来等待子进程的结束。</p>
<p>一个子进程向父进程返回一个值，所以父进程必须接受这个值并处理。</p>
<p>wait()系统调用担任这个要求：</p>
<ul>
<li>它使父进程去睡眠来等待子进程的结果；</li>
<li>当一个子进程调用exit()的时候，操作系统解锁父进程，并且将通过exit()传递得到的返回值作为wait()调用的一个结果（连同子进程的pid一起），如果这里没有子进程存活，wait()立刻返回；</li>
<li>当然，如果这里有为父进程的僵尸等待，wait()立即返回其他一个值（并且解锁僵尸状态）。</li>
</ul>
<p>子进程的PCB释放需要父进程来进行，所以需要wait()等待，让子进程结束后，父进程才结束。</p>
<p>进程结束执行之后，它调用exit()。</p>
<p>这个系统调用：</p>
<ul>
<li>将程序的结果作为一个参数</li>
<li>关闭所有打开的文件，连接等等</li>
<li>释放内存</li>
<li>释放大部分支持进程的操作系统结构</li>
<li>检查是否父进程存活着的：<ul>
<li>如果是的话，它保留结果直到父进程需要它；在这种情况里，进程没有真正死亡，但是它进入了僵尸状态；</li>
<li>如果没有，它释放所有的数据结构，这个进程死亡。这个由系统根进程（第一个创建的进程init）来代替父进程释放PCB。</li>
</ul>
</li>
<li>清理所有等待的僵尸进程</li>
</ul>
<p>进程控制的4个主要相关的系统调用与进程状态的关系：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191028122644.png" alt=""></p>
<p>调用exec()时，对应不同状态。</p>
<h2 id="调度算法"><a href="#调度算法" class="headerlink" title="调度算法"></a>调度算法</h2><p>状态之间的转化，都会触发调度。</p>
<p>内核运行调用程序的条件：（满足一条即可）</p>
<ul>
<li>一个进程从运行状态切换到等待状态</li>
<li>一个进程被终结了</li>
</ul>
<p>不可抢占：</p>
<ul>
<li>调度程序必须等待时间结束，一个进程处于阻塞状态，另一个进程不得不等待上一个进程执行完后再执行。</li>
</ul>
<p>可以抢占：</p>
<ul>
<li>调度程序在中断被响应后执行</li>
<li>当前的进程从运行切换到就绪，或者一个进程从等待切换到就绪</li>
<li>当前运行的进程可以被换出</li>
</ul>
<p>用户态可以抢占，内核态可抢占。</p>
<h3 id="调度原则"><a href="#调度原则" class="headerlink" title="调度原则"></a>调度原则</h3><ul>
<li>CPU使用率</li>
<li>吞吐量</li>
<li>周转时间：一个进程从初始化到结束，包括所有等待时间所花费的时间，周转时间=等待时间+处理时间</li>
<li>等待时间：进程在就绪队列中的总时间</li>
<li>响应时间：从一个请求被提交到产生第一次响应所花费的总时间</li>
</ul>
<p>具体的平均原则：</p>
<ul>
<li>减少响应时间：及时处理用户的输出并且尽快将输出提供给用户</li>
<li>减少平均响应时间的波动</li>
<li>增加吞吐链<ul>
<li>减少开销</li>
<li>系统资源的高效利用</li>
</ul>
</li>
<li><p>减少等待时间：减少每个进程的等待时间</p>
</li>
<li><p>低延迟调度增加了交互式表现</p>
</li>
<li>但是操作系统需要保证吞吐链不受影响</li>
<li>吞吐量是操作系统的计算带宽</li>
<li>响应时间是操作系统的计算延迟</li>
</ul>
<p>公平的定义：</p>
<p>举例：</p>
<ul>
<li>保证每个进程占用相同的CPU时间</li>
<li>这公平么？如果一个用户比其他用户运行更多的进程怎么办</li>
</ul>
<p>举例：</p>
<ul>
<li>保证每个进程都等待相同的时间</li>
</ul>
<p>公平通常回增加平均响应时间。</p>
<h3 id="通用计算机调度算法"><a href="#通用计算机调度算法" class="headerlink" title="通用计算机调度算法"></a>通用计算机调度算法</h3><h4 id="FCFS-先来先服务"><a href="#FCFS-先来先服务" class="headerlink" title="FCFS(先来先服务)"></a>FCFS(先来先服务)</h4><p>如果进程在执行中阻塞，队列中的第一个会得到CPU。</p>
<p>举例：3个进程，计算时间分别为12、3、3</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191101143543.png" alt=""></p>
<p>优点：简单</p>
<p>缺点：</p>
<ul>
<li>平均等待时间波动大</li>
<li>花费时间少的任务可能排在花费时间长的任务后面</li>
<li>可能导致I/O和CPU之间重叠处理</li>
</ul>
<h4 id="SJF-短作业优先"><a href="#SJF-短作业优先" class="headerlink" title="SJF(短作业优先)"></a>SJF(短作业优先)</h4><p>按照预测完成时间来将任务入队</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191101144026.png" alt=""></p>
<p>就绪队列中的进程按照预测时间进行了排序。</p>
<p>可以是抢占的或者不抢占的：</p>
<ul>
<li>不抢占的：如果一个进程在执行过程中，来一个新的进程，而且新的进程执行时间比当前执行的进程时间还要短，采取的策略是不打断当前执行的进程，而是放入就绪队列的开头</li>
<li>抢占的：如果当前进程的需要9个时间片，而刚执行完成一个时间片，并且新来的进程只需要5个时间片，采取的策略则是打断当前执行的进程，从运行态变成就绪态，而新来的进程占用CPU执行。也成为SRT(最短剩余时间)。</li>
</ul>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191101144757.png" alt=""></p>
<p>存在的问题：</p>
<ul>
<li>可能导致饥饿<ul>
<li>连续的短任务流使长任务饥饿</li>
<li>短任务可用时的任何长任务的CPU时间都会增加平均等待时间</li>
</ul>
</li>
<li>需要预知未来<ul>
<li>怎么预估下一个CPU突发的持续时间</li>
<li>简单的解决办法：询问用户</li>
<li>如果用户欺骗就杀死进程</li>
<li>如果用户不知道怎么办</li>
</ul>
</li>
</ul>
<p>根据过去来预测未来。</p>
<h4 id="HRRN-最高响应比优先"><a href="#HRRN-最高响应比优先" class="headerlink" title="HRRN(最高响应比优先)"></a>HRRN(最高响应比优先)</h4><ul>
<li><p>在SPN调度的基础上改进</p>
</li>
<li><p>不可抢占</p>
</li>
<li><p>关注进程等待了多长时间</p>
</li>
<li><p>防止无限期推迟</p>
</li>
</ul>
<p>调度原则：选择R值（响应比）最高的进程<br>$$<br>R=(w+s)/s \<br>w：等待时间，s执行时间<br>$$</p>
<h4 id="Round-Robin-轮询"><a href="#Round-Robin-轮询" class="headerlink" title="Round Robin(轮询)"></a>Round Robin(轮询)</h4><p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191101150559.png" alt=""></p>
<p>RR开销：额外的上下文切换</p>
<p>时间片太大：</p>
<ul>
<li>等待时间过长</li>
<li>极限情况退化成FCFS</li>
</ul>
<p>时间片太小：</p>
<ul>
<li>反应迅速，但是….</li>
<li>吞吐量由于大量的上下文切换开销受到影响</li>
</ul>
<p>目标：</p>
<ul>
<li>选择一个合适的时间片</li>
<li>经验规则：维持上下文切换开销处于1%以内</li>
</ul>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191101150917.png" alt=""></p>
<h4 id="Multilevel-Feedback-Queues-多级反馈队列"><a href="#Multilevel-Feedback-Queues-多级反馈队列" class="headerlink" title="Multilevel Feedback Queues(多级反馈队列)"></a>Multilevel Feedback Queues(多级反馈队列)</h4><p>就绪队列划分成独立的队列：</p>
<ul>
<li>前台（交互） </li>
<li>后台（批处理）</li>
</ul>
<p>每个队列拥有自己的调度策略：</p>
<ul>
<li>前台：RR</li>
<li>后台：FCFS</li>
</ul>
<p>调度必须在队列间进行：</p>
<ul>
<li>固定优先级<ul>
<li>先处理前台，然后处理后台</li>
<li>可能导致饥饿</li>
<li>进程可能是动态变化，比如从前台变成后台</li>
</ul>
</li>
<li>时间切片<ul>
<li>每个队列都得到一个确定的能够调度其进程的CPU总时间</li>
<li>Eg：80%给使用RR的前台，20%给使用FCFS的后台</li>
</ul>
</li>
</ul>
<p>一个进程可以在不同的队列中移动。</p>
<p>进程是一个开始前台进程，优先级比较高，运算结束，会有大量的IO处理，等待时间较长，这样可以将其优先级提高。过一段时间，做完交互后，需要大量计算，是CPU密集，时间片用得比较快，用完一个时间片，将其优先级降低一级，逐渐移动到优先级比较低的队列中。交互性进程可以放在优先级比较到的队列中。</p>
<p>例如：n级优先级—优先级调度在所有级别中，RR在每个级别中</p>
<ul>
<li>时间片大小随优先级级别增加而增加</li>
<li>如果任务在当前的时间片中没有完成，则降到下一个优先级</li>
</ul>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191101151718.png" alt=""></p>
<h4 id="Fair-Share-Scheduling-公平共享调度"><a href="#Fair-Share-Scheduling-公平共享调度" class="headerlink" title="Fair Share Scheduling(公平共享调度)"></a>Fair Share Scheduling(公平共享调度)</h4><p>主要针对多人共享一台计算机时使用。</p>
<p>Linux采用了公平调度策略。</p>
<h4 id="总结"><a href="#总结" class="headerlink" title="总结"></a>总结</h4><ul>
<li>FCFS<ul>
<li>不公平，平均等待时间较差</li>
</ul>
</li>
<li>SPN/SRT短进程优先<ul>
<li>不公平，但是平均等待时间最小</li>
<li>需要精确预测计算时间</li>
<li>可能导致饥饿</li>
</ul>
</li>
<li>HRRN最高响应比优先<ul>
<li>基于SPN调度改进</li>
<li>不可抢占</li>
</ul>
</li>
<li>RR轮询<ul>
<li>公平，但是平均等待时间较差</li>
</ul>
</li>
<li>MLFQ 多级反馈队列<ul>
<li>和SPN类似</li>
</ul>
</li>
<li>FSS公平共享调度<ul>
<li>公平是第一要素</li>
</ul>
</li>
</ul>
<h3 id="实时调度"><a href="#实时调度" class="headerlink" title="实时调度"></a>实时调度</h3><p>实时调度一般用于实时系统，用在工业控制，比如火车、机床等等。规定时间完成一定任务。</p>
<ul>
<li><p>强实时系统：需要在保证的时间内完成重要的任务，必须完成</p>
</li>
<li><p>弱实时系统：要求重要的进程的优先级更高，尽量完成，并费必须</p>
</li>
</ul>
<p>任务（工作单元）：一次计算、一次文件读取、一次信息传递等等</p>
<h4 id="RM速度单调调度"><a href="#RM速度单调调度" class="headerlink" title="RM速度单调调度"></a>RM速度单调调度</h4><h4 id="EDF最早期限调度"><a href="#EDF最早期限调度" class="headerlink" title="EDF最早期限调度"></a>EDF最早期限调度</h4><h3 id="多处理器调度"><a href="#多处理器调度" class="headerlink" title="多处理器调度"></a>多处理器调度</h3><p>多处理器的CPU调度更加复杂。</p>
<p>对称多处理器(SMP)。</p>
<h3 id="优先级反转问题"><a href="#优先级反转问题" class="headerlink" title="优先级反转问题"></a>优先级反转问题</h3><p>$T_3$、$T_1$、$T_2$三者优先级从低到高。$t_1$时刻$T_3$进入开始执行，到$t_2$时刻开始读取缓冲区，缓冲区被上锁，直到$t_3$时刻，$T_1$进程进入，由于其优先级高于$T_3$，所以$T_1$开始执行，到$t_4$时刻，$T_1$同样需要读取缓冲区，但是缓存区被$T_3$上锁导致无法读取，所以$T_3$继续执行。到了$t_5$时刻，进程$T_2$进入，由于$T_2$优先级高于$T_3$，所以$T_2$开始执行，直到$T_2$执行完毕。这是$T_3$继续执行，$T_3$完成缓冲区读取，将缓冲区解锁，由于$T_1$的优先级高于$T_3$，所以$T_1$继续执行。</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191101171904.png" alt=""></p>
<p>解决办法：</p>
<ul>
<li>优先级任务继承高优先级任务的优先级依赖于他们的共享的资源</li>
<li>优先级天花板：“资源”的优先级和“所有可以锁定该资源的任务中的优先级最高的那个任务”的优先级相同</li>
<li>除非优先级高于系统中所有被锁定的资源的优先级上限，否则任务尝试执行临界区的时候会被阻塞</li>
<li>持有最高优先级上限信号量锁的任务，会继承被该锁所阻塞的任务的优先级。</li>
</ul>
<h2 id="同步"><a href="#同步" class="headerlink" title="同步"></a>同步</h2><p>无论多个线程的指令序列怎么样交替执行，程序都必须正常工作。</p>
<h3 id="概念"><a href="#概念" class="headerlink" title="概念"></a>概念</h3><p><strong>原子操作</strong>是指一次不存在任何中断或者失败的执行</p>
<ul>
<li>该执行成功结束</li>
<li>或者根本没有执行</li>
<li>并且不应该发现任何部分执行的状态。</li>
</ul>
<p>实际上操作往往不是原子的。</p>
<p><strong>临界区：</strong>是指进程中的一段需要访问共享资源并且当另一个进程处于相应代码区域时便不会被执行的代码区域。</p>
<p><strong>互斥：</strong>当一个进程处于临界区并访问共享资源时，没有其他进程会处于临界区并且访问任何相同的共享资源。</p>
<p><strong>饥饿：</strong>一个可执行的进程，被调度器持续忽略，以至于虽然处于可执行状态却不被执行</p>
<p><strong>锁：</strong>只能等待解锁后才能访问</p>
<p><strong>解锁：</strong>使得可以访问之前被锁保护的物体类的东西</p>
<p><strong>死锁：</strong>两个或以上的进程，在相互等待完成特定任务，而最终没法将自身任务进行下去。A拿到锁1，B拿到锁2，A想继续拿到锁2后再继续执行，B想继续拿到锁1后再继续执行。导致A和B谁也无法继续执行。</p>
<h3 id="临界区"><a href="#临界区" class="headerlink" title="临界区"></a>临界区</h3><p><strong>互斥</strong>：同一时间临界区中最多存在一个线程</p>
<p><strong>Progress：</strong>如果一个线程想要进入临界区，那么它最终会成功</p>
<p><strong>有限等待</strong>：如果一个线程i处于入口区，那么在i的请求被接收之前，其他线程进入临界区的时间是有限制的</p>
<p><strong>无忙等待（可选）</strong>：如果一个进程在等待进入临界区，那么在它可以进入之前会被挂起</p>
<h3 id="禁用硬件中断"><a href="#禁用硬件中断" class="headerlink" title="禁用硬件中断"></a>禁用硬件中断</h3><p>没有中断，没有上下文切换，因此没有并发。</p>
<p>进入临界区，禁用中断</p>
<p>离开临界区，开启中断</p>
<p>缺点：</p>
<ul>
<li>一旦中断被禁用，线程就无法被停止<ul>
<li>整个系统都会为你停下来</li>
<li>可能导致其他线程处于饥饿状态</li>
</ul>
</li>
<li>要是临界区可以任意长<ul>
<li>无法限制响应中断所需的时间（可能存在硬件影响）</li>
</ul>
</li>
<li><p>要小心使用</p>
</li>
<li><p>多CPU下无法解决，因为只能关闭当前CPU的中断，其他CPU还是可以执行临界区</p>
</li>
</ul>
<h3 id="基于软件的解决办法"><a href="#基于软件的解决办法" class="headerlink" title="基于软件的解决办法"></a>基于软件的解决办法</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">do</span>&#123;</span><br><span class="line">    </span><br><span class="line">&#125;<span class="keyword">while</span>(<span class="number">1</span>);</span><br></pre></td></tr></table></figure>
<p>共享变量：</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">int</span> turn = <span class="number">0</span>;</span><br><span class="line">turn == i <span class="comment">//表示该谁进入临界区</span></span><br><span class="line">Thread Ti</span><br><span class="line"><span class="keyword">do</span>&#123;</span><br><span class="line">    <span class="keyword">while</span>(turn != i);  </span><br><span class="line">    critical section</span><br><span class="line">    turn = j;</span><br><span class="line">    reminder section</span><br><span class="line">&#125;<span class="keyword">while</span>(<span class="number">1</span>);</span><br></pre></td></tr></table></figure>
<p>满足互斥，但是有时不满足progress(前进)。即$T_i$做其他的事情，$T_j$想要继续运行，但是必须等待$T_i$处理临界区。</p>
<p>共享变量初始化：</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">int</span> flag[<span class="number">2</span>]; flag[<span class="number">0</span>] = flag[<span class="number">1</span>] = <span class="number">0</span>;</span><br><span class="line">flag[i] == <span class="number">1</span><span class="comment">//指示进程是否准备好进入临界区</span></span><br><span class="line"></span><br><span class="line">Thread Ti;</span><br><span class="line"><span class="keyword">do</span>&#123;</span><br><span class="line">    <span class="keyword">while</span>(flag[j] == <span class="number">1</span>); <span class="comment">//判断别的进程是否进入了临界区</span></span><br><span class="line">   	flag[i] = <span class="number">1</span>;</span><br><span class="line">    critical section;</span><br><span class="line">    flag[i] = <span class="number">0</span>;</span><br><span class="line">    remainder section</span><br><span class="line">&#125;<span class="keyword">while</span>(<span class="number">1</span>);</span><br></pre></td></tr></table></figure>
<p>不满足互斥，开始时刻，flag[1]和flag[0]都为0，可以跳过while循环，从而将flag[0]和flag[1]都设为1，从而可以继续执行。</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">int</span> flag[<span class="number">2</span>]; flag[<span class="number">0</span>] = flag[<span class="number">1</span>] = <span class="number">0</span>;</span><br><span class="line">flag[i] == <span class="number">1</span><span class="comment">//指示进程是否准备好进入临界区</span></span><br><span class="line"></span><br><span class="line">Thread Ti;</span><br><span class="line"><span class="keyword">do</span>&#123;</span><br><span class="line">    flag[i] = <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">while</span>(flag[j] == <span class="number">1</span>); <span class="comment">//判断别的进程是否进入了临界区</span></span><br><span class="line">    critical section;</span><br><span class="line">    flag[i] = <span class="number">0</span>;</span><br><span class="line">    remainder section</span><br><span class="line">&#125;<span class="keyword">while</span>(<span class="number">1</span>);</span><br></pre></td></tr></table></figure>
<p>满足互斥，但是存在死锁。进程0将flag[0]设为1，然后切换到进程1，进程1将flag[1]设为1，此时两个进程都无法继续执行。</p>
<p><strong>正确的解法：</strong>Deeker算法</p>
<p>使用两个共享的变量。</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">int</span> turn;  <span class="comment">//指示该谁进入临界区</span></span><br><span class="line"><span class="keyword">bool</span> flag[]; <span class="comment">//指示进程是否准备好进入临界区</span></span><br></pre></td></tr></table></figure>
<p>Code for ECTER_CRITICAL_SECTION</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">flag[i] = <span class="literal">true</span>;</span><br><span class="line">turn = j;</span><br><span class="line"><span class="keyword">while</span> (flag[j] &amp;&amp; turn == j);</span><br></pre></td></tr></table></figure>
<p>Code for EXIT_CRITICAL_SECTION</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">flag[i] = <span class="literal">false</span>;</span><br></pre></td></tr></table></figure>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">do</span>&#123;</span><br><span class="line">    flag[i] = <span class="literal">true</span>;</span><br><span class="line">	turn = j;</span><br><span class="line">	<span class="keyword">while</span> (flag[j] &amp;&amp; turn == j);</span><br><span class="line">    critical section</span><br><span class="line">    flag[i] <span class="literal">false</span>;</span><br><span class="line">    remainder section</span><br><span class="line">&#125;<span class="keyword">while</span>(<span class="number">1</span>);</span><br></pre></td></tr></table></figure>
<p>针对两个进程，满足互斥，满足有限等待，满足progress。</p>
<p>针对n个进程的互斥操作的保护。</p>
<ul>
<li>Bakery算法：取号排队，如果两个窗口取号，号码相等时，根据进程ID进行排序。</li>
<li>Eisenberg and McGuire算法</li>
</ul>
<h3 id="更高级的抽象"><a href="#更高级的抽象" class="headerlink" title="更高级的抽象"></a>更高级的抽象</h3><p>硬体提供了一些原语</p>
<ul>
<li>想中断禁用、原子操作指令</li>
</ul>
<p>操作系统提高了更高级的编程抽象来简化并行编程：</p>
<ul>
<li>锁，信号量</li>
<li>从硬件原语中构建</li>
</ul>
<p>锁是一个抽象的数据结构：</p>
<ul>
<li>一个二进制状态：锁定/解锁</li>
<li>Lock::Acquire()：获取锁</li>
<li>Lock::Release()：释放锁</li>
</ul>
<p><strong>原子操作指令：</strong></p>
<p>Test-and-set指令：测试和置位，完成3个指令</p>
<ul>
<li>从内存中读取值</li>
<li>测试该值是否为1，然后返回真或假</li>
<li>内存值设置为1</li>
</ul>
<p>Exchange指令：交换</p>
<ul>
<li>交换内存中的两个值</li>
</ul>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">bool</span> <span class="title">TestAndSet</span><span class="params">(<span class="keyword">bool</span> * target)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">bool</span> rv = *target;</span><br><span class="line">    *target = <span class="literal">true</span>;</span><br><span class="line">    <span class="keyword">return</span> rv;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">Exchange</span><span class="params">(<span class="keyword">bool</span> *a, <span class="keyword">bool</span> *b)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">bool</span> temp = *a;</span><br><span class="line">    *a = *b;</span><br><span class="line">    *b = temp;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>虽然这两个指令，语义上由多个小的指令完成，但是它们被封装成了机器指令，在指令中间，不会产生中断和切换。</p>
<p>利用这两个指令，来设计进入和退出临界区的代码。</p>
<p><strong>利用test-and-set实现：</strong></p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Lock</span>&#123;</span></span><br><span class="line">    <span class="keyword">int</span> value = <span class="number">0</span>;</span><br><span class="line">&#125;;</span><br><span class="line"></span><br><span class="line"><span class="comment">//如果锁被释放，那么test-and-set读取0并将值设置为1 -&gt;锁被设置为忙并且需要等待完成</span></span><br><span class="line"><span class="comment">//如果锁处于忙状态，那么test-and-set读取并将值设置为1-&gt;不改变锁的状态并且需要循环</span></span><br><span class="line">Lock::Acquire()&#123;</span><br><span class="line">    <span class="keyword">while</span>(test-<span class="keyword">and</span>-<span class="built_in">set</span>(value));</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">Lock::Release()&#123;</span><br><span class="line">    value = <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>不仅支持两个进程，还支持多个进程。</p>
<p>可以改进的地方：</p>
<ul>
<li>使用忙等待的锁</li>
</ul>
<p>无忙等待</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Lock</span>&#123;</span></span><br><span class="line">    <span class="keyword">int</span> value = <span class="number">0</span>;</span><br><span class="line">    WaitQueue q;</span><br><span class="line">&#125;;</span><br><span class="line"></span><br><span class="line">Lock::Acquire()&#123;</span><br><span class="line">    <span class="keyword">while</span>(test-<span class="keyword">and</span>-<span class="built_in">set</span>(value))&#123;</span><br><span class="line">        add <span class="keyword">this</span> TCB to wait <span class="built_in">queue</span> q;</span><br><span class="line">        schedule();</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">Lock::Release()&#123;</span><br><span class="line">    value = <span class="number">0</span>;</span><br><span class="line">    remove one thread t from q;</span><br><span class="line">    wakeup(t);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p><strong>使用exchange的实现：</strong></p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">int</span> key;</span><br><span class="line"><span class="keyword">int</span> lock = <span class="number">0</span>;</span><br><span class="line"><span class="keyword">do</span>&#123;</span><br><span class="line">    key = <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">while</span> (key == <span class="number">1</span>) exchage(lock, key);</span><br><span class="line">    critical section;</span><br><span class="line">    lock = <span class="number">0</span>;</span><br><span class="line">    remainder section</span><br><span class="line">&#125;<span class="keyword">while</span>(<span class="number">1</span>);</span><br></pre></td></tr></table></figure>
<p>也可以设计基于无忙等的锁。</p>
<p>缺点：</p>
<ul>
<li>忙等待消耗处理器时间</li>
<li>当进程离开临界区并且多个进程在等待的时候可能导致饥饿</li>
<li>死锁<ul>
<li>如果一个低优先级的进程拥有临界区并且一个高优先级进程也需要，那么高优先级进程会获得处理器并等待临界区。</li>
</ul>
</li>
</ul>
<h3 id="信号量"><a href="#信号量" class="headerlink" title="信号量"></a>信号量</h3><p>一个整型sem，两个原子操作：</p>
<ul>
<li>P()：sem减1，如果sem&lt;0，等待，否则继续</li>
<li>V()：sem加1，如果sem&lt;=0，唤醒一个等待的P</li>
</ul>
<p>Dijkstar提出的，V：是荷兰语增加，P是荷兰语的减少。</p>
<p>信号量是一个<strong>有符号的整数</strong>，信号量是<strong>被保护</strong>的变量。</p>
<p>P()能够阻塞，V()不会阻塞。</p>
<p>两种类型信号量：</p>
<ul>
<li>二进制信号量：可以是0或1</li>
<li>一般/计数信号量：可取任何非负值</li>
</ul>
<p>信号量可以用在2个方面：</p>
<ul>
<li>互斥</li>
<li>条件同步</li>
</ul>
<h3 id="信号量使用"><a href="#信号量使用" class="headerlink" title="信号量使用"></a>信号量使用</h3><p>使用二进制信号量，可以代替锁：</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line">mutex = <span class="keyword">new</span> Semaphore(<span class="number">1</span>);</span><br><span class="line">mutex-&gt;P();</span><br><span class="line">...</span><br><span class="line">critical section</span><br><span class="line">mutex-&gt;V();</span><br></pre></td></tr></table></figure>
<p>用二进制信号量实现调度约束：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191104161206.png" alt=""></p>
<p>Thread A的P()之后的操作，需要先等待Thread B的V()操作执行后，才能执行。</p>
<p><strong>生产者和消费者模型</strong></p>
<ul>
<li><p>一个或多个生产者产生数据将数写入缓存区中</p>
</li>
<li><p>单个消费者每次从缓存区中读取数据</p>
</li>
<li><p>在任何一个时间只有一个生产者或消费者可以访问缓冲区</p>
</li>
</ul>
<p>正确性要求：</p>
<ul>
<li>在任何一个时间只能一个线程操作缓存区（互斥）</li>
<li>当缓存区为空，消费者必须等待生产者（调度/同步约束）</li>
<li>当缓存区满，生产者必须等待消费者（调度/同步约束）</li>
</ul>
<p>互斥机制和同步机制：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191104160210.png" alt=""></p>
<p>首先，初始化信号量，一个mutex互斥信号量，初始化为1；缓存区满信号量fullBuffers，初始化为0，表示一开始缓存区为空；缓存区为空信号量emptyBuffers，初始化在为n。</p>
<p>生产者Deposit()，消费者Remove()。</p>
<p>通过互斥信号量mutex来保证互斥。将Add c to the buffer包括起来，保证只能有一个线程操作buffer。</p>
<p>如果buffer没有满，可以继续执行，执行emptyBuffers的P操作，将emptybuffers减1，还是大于0，继续执行，最后执行fullBuffers的V操作，将fullBuffers加1，通知消费者执行。</p>
<p>消费者，首先执行fullBuffers的P()操作。对于首先生产者执行，因为末尾执行了fullBuffers的V操作，所以对于消费者可以继续执行。如果首先消费者执行，fullBuffers初始值为0，先执行减1，消费者进程进入等待，直到生产者进程执行fullBuffers的V操作，将fullBuffers变成0，消费者进程继续执行。</p>
<p>消费者最后执行emptyBuffers的V操作，是的emptyBuffers加1，使得睡眠在emptyBuffers-&gt;P()处的进程继续执行。</p>
<p><strong>注意：</strong>P的操作顺序不能变，否则会产生死锁。V的操作顺序可以变，因为V没有进行阻塞操作。</p>
<p>可以尝试交换生产者的empytBuffers-&gt;P()和mutex-&gt;P()操作试试？</p>
<h3 id="信号量的实现"><a href="#信号量的实现" class="headerlink" title="信号量的实现"></a>信号量的实现</h3><p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191106204603.png" alt=""></p>
<p>信号量的双用途：</p>
<ul>
<li>互斥和条件同步</li>
<li>但等待条件是独立的互斥</li>
</ul>
<h3 id="管程"><a href="#管程" class="headerlink" title="管程"></a>管程</h3><p>目的：分离互斥和条件同步的关注</p>
<p>管程提出用在编程语言层面的，简化语言进行同步互斥的操作。</p>
<p>管程(monitor)：包含一系列共享变量，以及针对这些变量操作的函数的模块。</p>
<ul>
<li>一个锁：执行临界区</li>
<li>0或多个条件变量：等待/通知信号量用于管理并发访问共享数据</li>
</ul>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191106205334.png" alt=""></p>
<p>Lock:</p>
<ul>
<li>Lock::Acquire()：等待直到锁可用，然后抢占锁</li>
<li>Lock::Release()：释放锁，唤醒等待着如果有</li>
</ul>
<p>Condition Variable</p>
<ul>
<li>允许等待状态进入临界区</li>
<li>Wait()操作：释放锁，睡眠，重新获得锁返回后</li>
<li>Singnal()操作：唤醒等待者（或者所有等待者）</li>
</ul>
<p>条件变量实现：</p>
<ul>
<li>需要维护每个条件队列</li>
<li>线程等待的条件等待singal()</li>
</ul>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191106205811.png" alt=""></p>
<p>使用管程解决生产者消费者问题：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191106211051.png" alt=""></p>
<p>当执行Signal()，是当前正在执行的进程继续执行，还是让唤醒的进程执行？即下面的两种方式：Hoare和Hansen。</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191106211638.png" alt=""></p>
<p>Hoare实现起来比较困难，而Hansen实现起来比较容易，操作系统和语言就是采用该方法。</p>
<p>这两种方式对我们管程中条件变量的使用也会产生影响。</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191106211822.png" alt=""></p>
<p>总结：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191106212416.png" alt=""></p>
<h3 id="经典同步问题"><a href="#经典同步问题" class="headerlink" title="经典同步问题"></a>经典同步问题</h3><h4 id="读者-写者问题"><a href="#读者-写者问题" class="headerlink" title="读者-写者问题"></a>读者-写者问题</h4><p>读者：不需要修改数据</p>
<p>写者：读取和修改操作</p>
<p>问题的约束：</p>
<ul>
<li>允许同一时间有多个读者，但在任何时候只有一个写者</li>
<li>当没有写者时，读者才能访问数据</li>
<li>当没有读者和写着时，写者才能访问数据</li>
<li>在任何时候只能有一个线程可以操作共享变量</li>
</ul>
<p><strong>读者优先</strong>：如果有读者在读数据，并且有写者在等待，这个时候来了一个读者，读者可以跳过等待的写着，当当前读者读完，刚来的读者可以继续读。</p>
<p>共享数据：</p>
<ul>
<li>数据集</li>
<li>信号量CountMutex初始化为1，保证只有一个读者读取数据</li>
<li>信号量WriteMutex初始化为1，保证只有一个写着写数据</li>
<li>整数Rcount初始化为0初始化为0，当前有多少个读者</li>
</ul>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191107110330.png" alt=""></p>
<p><strong>写者优先</strong>：一旦写着就绪，那么写着会尽可能第执行写操作。如果写着源源不断地出现，那么读者就始终处于阻塞状态。</p>
<p>当当前有写者正在执行，或者当前读者等待队列不为空，读者都需要等待。</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191107111005.png" alt=""></p>
<p>对于读者：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191107111808.png" alt=""></p>
<p>对于写者：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191107121302.png" alt=""></p>
<p>broadcast()唤醒条件变量队列中的所有进程。</p>
<h4 id="哲学家就餐问题"><a href="#哲学家就餐问题" class="headerlink" title="哲学家就餐问题"></a>哲学家就餐问题</h4><p>问题描述：5个哲学家围绕一张圆桌而坐，桌子上放着5支叉子，每两个哲学家之间放一支；哲学家的动作包括思考和进餐，进餐时需要同时拿起他左边和右边的两只叉子，思考时则同时将两支叉子返回原处。如果保证哲学家们的动作有序进行？如：不出现有人永远拿不到叉子。</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191108143447.png" alt=""></p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">define</span> N 5                 <span class="comment">//哲学家个数</span></span></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">philosopher</span><span class="params">(<span class="keyword">int</span> i)</span>     <span class="comment">//i哲学家编号</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">while</span>(<span class="number">1</span>)</span><br><span class="line">    &#123; </span><br><span class="line">        think();            <span class="comment">//哲学家思考</span></span><br><span class="line">        take_fork(i);       <span class="comment">//去拿左边的叉子</span></span><br><span class="line">        take_fork((i+<span class="number">1</span>)%N); <span class="comment">//去拿右边的叉子</span></span><br><span class="line">        eat();              <span class="comment">//吃饭</span></span><br><span class="line">        put_fork(i);        <span class="comment">//放下左边的叉子</span></span><br><span class="line">        put_fork((i+<span class="number">1</span>)%N);  <span class="comment">//放下右边的叉子</span></span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>上面方法会出现死锁。5个进程同时处理，第一步5个人都在思考，第二步，5个人同时拿左边的叉子。到第三步的时候，5个哲学家都无法拿到右边的叉子，并且无法释放左边的叉子，从而导致死锁。</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">define</span> N 5                 <span class="comment">//哲学家个数</span></span></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">philosopher</span><span class="params">(<span class="keyword">int</span> i)</span>     <span class="comment">//i哲学家编号</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    think();            <span class="comment">//哲学家思考</span></span><br><span class="line">    <span class="keyword">while</span>(<span class="number">1</span>)                <span class="comment">//去拿两把叉子</span></span><br><span class="line">    &#123;</span><br><span class="line">        take_fork(i);       <span class="comment">//去拿左边的叉子</span></span><br><span class="line">        <span class="keyword">if</span> (fork(i+<span class="number">1</span>)%N)&#123;       <span class="comment">//右边叉子还在吗？</span></span><br><span class="line">            take_fork((i+<span class="number">1</span>)%N); <span class="comment">//去拿右边的叉子</span></span><br><span class="line">            <span class="keyword">break</span>;</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;                  <span class="comment">//右边叉子不在了</span></span><br><span class="line">            put_fork(i);        <span class="comment">//放下左边的叉子</span></span><br><span class="line">            wait_some_time();    <span class="comment">//等一会</span></span><br><span class="line">        &#125; </span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>对拿叉子的过程进行了改进，但仍不正确。首先，5个进程同时开始执行，同时拿到左边的叉子，然后执行else里面的操作，放回叉子，等待相同的时间，继续去拿左边的叉子，出现了死循环。</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">define</span> N 5                 <span class="comment">//哲学家个数</span></span></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">philosopher</span><span class="params">(<span class="keyword">int</span> i)</span>     <span class="comment">//i哲学家编号</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    think();            <span class="comment">//哲学家思考</span></span><br><span class="line">    <span class="keyword">while</span>(<span class="number">1</span>)                <span class="comment">//去拿两把叉子</span></span><br><span class="line">    &#123;</span><br><span class="line">        take_fork(i);       <span class="comment">//去拿左边的叉子</span></span><br><span class="line">        <span class="keyword">if</span> (fork(i+<span class="number">1</span>)%N)&#123;       <span class="comment">//右边叉子还在吗？</span></span><br><span class="line">            take_fork((i+<span class="number">1</span>)%N); <span class="comment">//去拿右边的叉子</span></span><br><span class="line">            <span class="keyword">break</span>;</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;                  <span class="comment">//右边叉子不在了</span></span><br><span class="line">            put_fork(i);        <span class="comment">//放下左边的叉子</span></span><br><span class="line">            wait_random_time();    <span class="comment">//等待随机长时间</span></span><br><span class="line">        &#125; </span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>等待时间随机变化。可行，但非万全之策。</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line">semaphore mutex;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">philosopher</span><span class="params">(<span class="keyword">int</span> i)</span>     <span class="comment">//i哲学家编号</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">while</span>(<span class="number">1</span>)</span><br><span class="line">    &#123; </span><br><span class="line">        think();            <span class="comment">//哲学家思考</span></span><br><span class="line">        P(mutex);</span><br><span class="line">            take_fork(i);       <span class="comment">//去拿左边的叉子</span></span><br><span class="line">            take_fork((i+<span class="number">1</span>)%N); <span class="comment">//去拿右边的叉子</span></span><br><span class="line">            eat();              <span class="comment">//吃饭</span></span><br><span class="line">            put_fork(i);        <span class="comment">//放下左边的叉子</span></span><br><span class="line">            put_fork((i+<span class="number">1</span>)%N);  <span class="comment">//放下右边的叉子</span></span><br><span class="line">        V(mutex);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>互斥访问。方案正确。但是每次只允许一个人进餐。效率太低。把就餐堪称必须互斥访问的临界资源，因此会造成资源的浪费。</p>
<p>从理论上来说，如果有5把叉子，应该允许不相邻的哲学家同时进餐。</p>
<p>改进思路：</p>
<ul>
<li><p>S1: 思考中…</p>
</li>
<li><p>S2：进入饥饿状态</p>
</li>
<li>S3：如果左邻居和右邻居正在进餐，进程进入阻塞状态，否则转S4</li>
<li>S4：拿起两把叉子</li>
<li>S5：吃面条</li>
<li>S6：放下左边的叉子，看看左邻居现在能否进餐（饥饿状态，两把叉子都在），若能则唤醒之</li>
<li>S7：放下右边的叉子，看看右邻居现在能否进餐（饥饿状态，两把叉子都在），若能则唤醒之</li>
<li>新的一天又开始了，转S1</li>
</ul>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">define</span> N 5                 <span class="comment">//哲学家个数</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> LEFT i              <span class="comment">//第i个哲学家的左邻剧</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> RIGHT (i+1)%N       <span class="comment">//第i个哲学家的右邻居</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> THINKING 0          <span class="comment">//思考状态</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> HUNGRY 1            <span class="comment">//饥饿状态</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> EATING 2            <span class="comment">//进餐状态</span></span></span><br><span class="line"><span class="keyword">int</span> state[N];               <span class="comment">//记录每个人的状态</span></span><br><span class="line"></span><br><span class="line"><span class="comment">//该状态是一个临界资源，对它的访问应该互斥地进行</span></span><br><span class="line">semaphore mutex;            <span class="comment">//互斥信号量，初值为1</span></span><br><span class="line"></span><br><span class="line"><span class="comment">//一个哲学家吃饱后，可能要唤醒邻居，存在同步关系</span></span><br><span class="line">semaphore s[N];             <span class="comment">//同步信号量，初值为0</span></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">philosopher</span><span class="params">(<span class="keyword">int</span> i)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">while</span>(<span class="literal">true</span>)</span><br><span class="line">    &#123;</span><br><span class="line">        think();           <span class="comment">//对应S1,思考中</span></span><br><span class="line">        take_forks(i);     <span class="comment">//对应S2-S4,拿到两把叉子或被阻塞</span></span><br><span class="line">        eat();             <span class="comment">//对应S5，吃面条中，不需要任何设计</span></span><br><span class="line">        put_forks();       <span class="comment">//对应S7-S8，把两把叉子放回原处</span></span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//功能：要么拿起两把叉子，要么被阻塞起来</span></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">tate_fork</span><span class="params">(<span class="keyword">int</span> i)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    P(mutex);           <span class="comment">//进入临界区，因为别的进程需要读取state[i]，来判断旁边的哲学家释放在进餐</span></span><br><span class="line">    state[i] = HUNGRY;  <span class="comment">//饥饿状态</span></span><br><span class="line">    test_take_left_right_forks(i);  <span class="comment">//试图拿起两把叉子</span></span><br><span class="line">    V(mutex);           <span class="comment">//退出临界区</span></span><br><span class="line">    P(s[i]]);           <span class="comment">//没有叉子阻塞，由于test_take_left_right_forks(i)中的V(s[i])进行了加1，所以不会阻塞</span></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">test_take_left_right_forks</span><span class="params">(<span class="keyword">int</span> i)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="comment">//我在饥饿状态，左邻剧和右邻居没有处于进餐状态</span></span><br><span class="line">    <span class="keyword">if</span> (state[i] == HUNGRY &amp;&amp; state[LEFT] != EATING &amp;&amp; state[RIGHT] != EATING)</span><br><span class="line">    &#123;</span><br><span class="line">        state[i] = EATING:       <span class="comment">//两把叉子到手</span></span><br><span class="line">        V(s[i]);                 <span class="comment">//通知第i人可以吃饭了，将s[i]加1，使得后面的P(s[i])不被阻塞</span></span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//功能：把两把叉子返回原处，并在需要的时候去唤醒左邻居和右邻居</span></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">put_forks</span><span class="params">(<span class="keyword">int</span> i)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    P(mutex);                                <span class="comment">//进入临界区，因为牵涉state[i]的赋值，所以要互斥保护</span></span><br><span class="line">    state[i] = THINKING;                     <span class="comment">//交出两把叉子</span></span><br><span class="line">    test_take_left_right_forks(LEFT);        <span class="comment">//看左邻剧能否进餐</span></span><br><span class="line">    test_take_left_right_forks(RIGHT);       <span class="comment">//看右邻居能否进餐                  </span></span><br><span class="line">    V(mutex);                                <span class="comment">//退出临界区</span></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">think</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    P(mutex);             <span class="comment">//进入临界区，因为牵涉state[i]的赋值，所以要互斥保护</span></span><br><span class="line">    state[i] = THINKING:  <span class="comment">//设为思考状态</span></span><br><span class="line">    V(mutex);             <span class="comment">//退出临界区</span></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="死锁"><a href="#死锁" class="headerlink" title="死锁"></a>死锁</h3><p>一组阻塞的进程持有一种资源等待获取另一个进程所占用的一个资源。由于并发执行导致，共享资源所有进程都可以去占用，而且资源是互斥的。</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191110094103.png" alt=""></p>
<p>如果图中不包含循环，没有死锁。</p>
<p>如果图中包含循环，如果每个资源类只有一个实例，那么没有死锁。</p>
<p>如果每个资源类有几个实例，可能死锁。</p>
<h4 id="死锁特征"><a href="#死锁特征" class="headerlink" title="死锁特征"></a>死锁特征</h4><p>四个条件同时成立：</p>
<ul>
<li><strong>互斥</strong>：在一个时间段内只能有一个进程使用资源</li>
<li><strong>持有并等待</strong>：进程保持至少一个资源正在等待获取其他进程持有的额外资源</li>
<li><strong>无抢占</strong>：一个资源只能被进程资源释放，进程已经完成了他的任务之后</li>
<li><strong>循环等待</strong>：存在等待进程集合${P_0, P_1,…,P_N}$，$P_0$正在等待$P_1$所占用的资源，$P_1$等待$P_2$占用的资源，…，$P_{N-1}$等待$P_N$占用的资源，$P_N$等待$P_0$所占用的资源。</li>
</ul>
<p>死锁的四个必要条件。一旦有了死锁，这四个条件不成立，但是这四个条件成立，不一定会产生死锁。</p>
<h4 id="死锁处理办法"><a href="#死锁处理办法" class="headerlink" title="死锁处理办法"></a>死锁处理办法</h4><ul>
<li>确保系统永远不进入死锁状态</li>
<li>运行系统进入死锁状态，然后恢复</li>
<li>忽略这个问题，假装系统中从来没有发生死锁；用于大多数操作系统，包括UNIX。</li>
</ul>
<p><strong>死锁预防</strong>：</p>
<p>打破死锁的4个必要条件之一：</p>
<ul>
<li>互斥：共享资源不是必须的，必须占用非共享资源，即将互斥资源并称非互斥资源，这个不太好。</li>
<li><p>持有并等待：必须保证当一个进程请求的资源，它不持有任何其他资源。所有资源都能拿到就继续执行，否则拿不到就睡眠。会导致资源利用率低，可能发生饥饿。</p>
</li>
<li><p>无抢占：如果进程占有某些资源，并请求其他不能被立即分配的资源，则释放当前正占用的资源。</p>
</li>
<li><p>循环等待：对所有资源类型进程排序，并要求每个进程按照资源的顺序进行申请。多用于嵌入式系统，资源类型有限。</p>
</li>
</ul>
<p><strong>死锁避免</strong>：</p>
<p>当进程申请资源时，判断申请的资源是否合理，即是否会产生死锁。</p>
<ul>
<li>每个进程声明它可能需要的每个类型资源的最大数目</li>
<li><p>资源的分配状态是通过限定提供和分配的资源数量，和进程的最大需求</p>
</li>
<li><p>死锁避免算法动态检查的资源分配状态，以确保永远不会有一个环形等待状态</p>
</li>
</ul>
<p><strong>死锁检测</strong>：</p>
<p>死锁检测允许系统进入死锁状态，如果检测到系统进入死锁状态，再进行恢复。</p>
<ul>
<li>Available(剩余空闲量)：长度为m的向量。如果$Available[j]=k$，表示有$k$个类型$R_j$的资源实例可用。</li>
<li>Allocation(已分配量)：n×m矩阵，，如果$Allocation[i,j]=k$，表示进程$P_i$当前分配了$R_j$的$k$个实例</li>
<li>Request：一个n×m矩阵表示各进程的当前请求。如果$Request[i,j]=k$，表示进程$P_i$请求$k$个资源$R_j$的实例</li>
</ul>
<p>死锁检测算法：</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//1. Work和Finish分别是长度为m与n的向量</span></span><br><span class="line">Work = Available;          <span class="comment">//Work当前空闲资源</span></span><br><span class="line"><span class="keyword">for</span> i = <span class="number">1</span>, <span class="number">2.</span>..n</span><br><span class="line">    <span class="keyword">if</span> Allocation[i] &gt; <span class="number">0</span></span><br><span class="line">		Finish[i] = <span class="literal">false</span>; <span class="comment">//Finish为线程是否可结束</span></span><br><span class="line">	<span class="keyword">else</span></span><br><span class="line">        Finish[i] = <span class="literal">true</span>;</span><br><span class="line"></span><br><span class="line"><span class="comment">//2. 找出这样的索引</span></span><br><span class="line">Finish[i] = <span class="literal">false</span>;        <span class="comment">//找到没有结束的进程，且此线程将需要的资源量小于当前空闲资源量</span></span><br><span class="line">Request[i] &lt;= Work;</span><br><span class="line">没找到这样的i，转到第<span class="number">4</span>步</span><br><span class="line">    </span><br><span class="line"><span class="comment">//3. 执行进程，释放资源</span></span><br><span class="line">Work = Work + Allocation[i]; <span class="comment">//把找到的线程拥有的资源释放回当前空闲资源中</span></span><br><span class="line">Finish[i] = <span class="literal">true</span>;             <span class="comment">//表示进程i可以结束</span></span><br><span class="line"></span><br><span class="line"><span class="comment">//4. 检测是否死锁</span></span><br><span class="line"><span class="keyword">for</span> some i, <span class="number">1</span> &lt;= i &lt;= n          <span class="comment">//如果有Finish[i]等于false，这表示系统处于死锁状态</span></span><br><span class="line">	<span class="keyword">if</span> Finish[i] = <span class="literal">false</span>    </span><br><span class="line">        系统处于死锁状态</span><br><span class="line">        P[i]死锁</span><br></pre></td></tr></table></figure>
<p>基于以下两个原因：</p>
<ul>
<li><p>开销比较大</p>
</li>
<li><p>需要获取每个进程需要的最大资源数量很困难</p>
</li>
</ul>
<p>银行家算法和死锁检测算法在系统中基本不会使用，一般来用检测。</p>
<p><strong>死锁恢复</strong>：</p>
<ul>
<li>终止所有的死锁进程</li>
<li>在一个时间内终止一个进程知道死锁消除</li>
<li>终止进程的顺序应该是：<ul>
<li>进程的优先级</li>
<li>进程运行了多久以及需要多少时间才能完成</li>
<li>进程占用的资源</li>
<li>进程完成需要的资源</li>
<li>多少进程需要被终止</li>
<li>进程是交互还是批处理</li>
</ul>
</li>
</ul>
<h4 id="银行家算法"><a href="#银行家算法" class="headerlink" title="银行家算法"></a>银行家算法</h4><p>银行家算法是一个死锁避免的著名算法。</p>
<p>银行家算法的前提：</p>
<ul>
<li>多个实例</li>
<li>每个进程都必须能最大限度地利用资源</li>
<li>当一个进程请求一个资源，就不得不等待</li>
<li>当一个进程获得所有的资源就必须在一段有限的时间释放它们</li>
</ul>
<p>基于上述前提条件，银行家算法通过尝试寻找允许每个进程获得的最大资源并结束的进程请求的一个理想执行时序，来决定一个状态是否是安全的。</p>
<p>不存在满足要求的执行时序的状态都是不安全的。</p>
<p>银行家算法数据结构:</p>
<p>n=进程数量， m= 资源类型数量</p>
<ul>
<li>Max(总需求量)：n×m矩阵，如果$Max[i,j]=k$，表示进程$P_i$最多请求资源类型$R_j$的$k$个实例</li>
<li>Available(剩余空闲量)：长度为m的向量。如果$Available[j]=k$，表示有$k$个类型$R_j$的资源实例可用。</li>
<li>Allocation(已分配量)：n×m矩阵，，如果$Allocation[i,j]=k$，表示进程$P_i$当前分配了$R_j$的$k$个实例</li>
<li>Need(未来需要量)：n×m矩阵，，如果$Need[i,j]=k$，表示进程$P_i$可能需要至少$R_j$的$k$个实例完成任务</li>
</ul>
<p>$$<br>Need[i,j]=Max[i,j] - Allocation[i,j]<br>$$</p>
<p>第一步：$Work$和$Finish$分别是长度为m和n的向量。</p>
<p>初始化：</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">Work = Available;      <span class="comment">//当前资源剩余空相良</span></span><br><span class="line">Finsh[i] = <span class="literal">false</span>;      <span class="comment">//进程i没结束，如果等于true，拥有了所有资源，可以执行并结束</span></span><br></pre></td></tr></table></figure>
<p>第二步：找这样的$i$</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">Finish[i] = false;</span><br><span class="line">Need[i,:] &lt;= Work</span><br></pre></td></tr></table></figure>
<p>没找到这样的$i$，转到第四步</p>
<p>第三步：</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">Work = Work + Allocation[i,:];    <span class="comment">//进程i的资源需求量小于当前剩余空闲资源量，所以分配资源给他执行，执行完成再回收</span></span><br><span class="line">Finish[i] = <span class="literal">true</span>;</span><br></pre></td></tr></table></figure>
<p>转到第二步</p>
<p>第四步：</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">if</span> Fininsh[i] == <span class="literal">true</span> <span class="keyword">for</span> all i  <span class="comment">//所有进程的Finish为true，表示系统处于安全状态</span></span><br><span class="line">    then the system is in a safe state</span><br><span class="line"> <span class="keyword">else</span>           <span class="comment">//不安全状态 </span></span><br><span class="line">     then the system is in a unsafe state</span><br></pre></td></tr></table></figure>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191110171506.png" alt=""></p>
<p>​    </p>
<p>例子：一个得到safe序列的例子。</p>
<p>得到一个安全的执行序列：P2-&gt;P1-&gt;P3-&gt;P4</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/safe.png" alt=""></p>
<p>例子：找出得到一个不安全状态。</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/unsafe.png" alt=""></p>
<p>首先分配给P1的资源为[1,0,1]，这样进入(b)阶段，可用资源变成了[0,1,1]，无法再满足现有进程的资源需求，这是一个不安全的状态。</p>
<h3 id="进程间通信-IPC"><a href="#进程间通信-IPC" class="headerlink" title="进程间通信(IPC)"></a>进程间通信(IPC)</h3><p>进程间通信可以分为间接通信(a)和直接通信(b):</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191111103036.png" alt=""></p>
<p>直接通信：</p>
<ul>
<li>进程必须证明的命名对方：<ul>
<li>send(P, message)，发送到进程P</li>
<li>reveive(Q, message)</li>
</ul>
</li>
</ul>
<p>间接通信：</p>
<ul>
<li>定向从消息队列接收消息<ul>
<li>每个消息队列都有一个唯一ID</li>
<li>只有它们共享了一个消息队列，进程才能通信</li>
</ul>
</li>
<li>原语的定义<ul>
<li>send(A, message)，发送到消息队列A</li>
<li>reveive(A, message)</li>
</ul>
</li>
</ul>
<p>消息传递可以是阻塞或非阻塞的：</p>
<ul>
<li>阻塞认为是同步的：即发送一个消息后等待返回消息，接收方等待一个消息直到收到消息</li>
<li>非阻塞认为是异步的：即发送方发送完消息，继续执行不等待返回结果</li>
</ul>
<p>通信链路缓冲：</p>
<ul>
<li>0容量：不缓冲，发送一个消息给对方，对方等待直到收到消息</li>
<li>有限容量：发送方一直往长度为n的buffer中写入数据，直到buffer满了；而接受发当buffer不为空的时候从缓冲区中读数据。</li>
<li>无限容量：不需要等待，但是接收方当buffer为空时不得不等待，理论分析采用</li>
</ul>
<h4 id="信号"><a href="#信号" class="headerlink" title="信号"></a>信号</h4><p>软件中断通知事件处理，发出一些通知信息。</p>
<p>接收到信号是处理：</p>
<ul>
<li>Catch：指定信号处理函数被调用</li>
<li>Ignore：依靠操作系统的默认操作</li>
<li>Mask：阻塞信号因此不会传送，可能是暂时的</li>
</ul>
<p>不足：不能传输要交互的任何数据，只能起到一种通知的作用。</p>
<p>首先，应用程序注册一个信号，发送给操作系统。</p>
<p>然后，操作系统内核收到信号，将另一个进程的堆栈信息中下一个执行入口切换为对应信号的函数。</p>
<p>最后，另一个应用程序开从信号对应的函数开始执行。</p>
<h4 id="管道"><a href="#管道" class="headerlink" title="管道"></a>管道</h4><p>管道是进行数据交换的。</p>
<p>Linux中的管道符<code>|</code>，比如<code>ls | more</code>的执行过程如下图：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191111105616.png" alt=""></p>
<p>管道其实就是内存中的一段缓冲区。</p>
<p>如果buffer满了，ls会被阻塞，但是当more消耗了buffer，就会唤醒ls进程。</p>
<p>shell的作用：</p>
<ul>
<li>创建管道</li>
<li>为ls创建一个进程，设置stdout为管道写端</li>
<li>为more创建一个进程，设置stdin为管道读端</li>
</ul>
<p><strong>管道必须有一个父进程。</strong>管道里面的数据是一种字节流。</p>
<h4 id="消息队列"><a href="#消息队列" class="headerlink" title="消息队列"></a>消息队列</h4><p>消息队列也是一种数据的传递机制。<strong>管道通过父进程帮子进程建立好通道。</strong>管道里面的数据是一种字节流。</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191111110214.png" alt=""></p>
<p>消息队列传递是一个某种结构，两个不同的进程可以来传输数据。这样是个结构化数据结构，接收方不用进行解析。<strong>同样缓冲区也是有限制的。</strong></p>
<h4 id="共享内存"><a href="#共享内存" class="headerlink" title="共享内存"></a>共享内存</h4><p>管道和消息队列是一种间接的通信方式。而共享内存是一种直接通信方式。</p>
<ul>
<li>每个进程都有私有地址空间</li>
<li>在每个地址空间内，明确地设置了共享内存段</li>
</ul>
<p>优点：</p>
<ul>
<li>快速，方便地共享数据</li>
</ul>
<p>不足:</p>
<ul>
<li>必须同步数据访问，采用同步互斥机制来保证</li>
</ul>
<p>通过将同一块物理内存映射到不同的进程的相同或不同的地址空间，通过虚地址访问不同进程的共享内存的虚地址其实访问的是同一块物理内存空间。</p>
<h4 id="socket"><a href="#socket" class="headerlink" title="socket"></a>socket</h4><p>网络部分的内容。虽然TCP和UDP实现在内核态。</p>
<h1 id="文件系统"><a href="#文件系统" class="headerlink" title="文件系统"></a>文件系统</h1><h2 id="基本概念"><a href="#基本概念" class="headerlink" title="基本概念"></a>基本概念</h2><p><strong>文件系统</strong>：一种用于持久性存储的系统抽象</p>
<p><strong>文件</strong>：文件系统中一个单元的相关数据结构在操作系统中的抽象</p>
<p>文件系统的功能：</p>
<ul>
<li>分配文件磁盘空间<ul>
<li>管理文件块（哪一块属于哪一个文件）</li>
<li>管理空闲空间（哪一块是空闲的）</li>
<li>分配算法（策略）</li>
</ul>
</li>
<li>管理文件集合<ul>
<li>定位文件及其内容</li>
<li>命名</li>
<li>最常见：分层文件系统</li>
</ul>
</li>
<li>提供便利及特征<ul>
<li>保护：分层来保护数据安全</li>
<li>可靠性/持久性：保持文件的持久即使发送崩溃，攻击等</li>
</ul>
</li>
</ul>
<p>文件：</p>
<ul>
<li>文件属性<ul>
<li>名称、类型、位置、大小、创建者、创建事件、最近修改事件</li>
</ul>
</li>
<li>文件头<ul>
<li>存储元数据中保存了每个文件的信息</li>
<li>保存文件的属性</li>
<li>跟踪哪一块存储块属于逻辑上文件结构的哪个便宜</li>
</ul>
</li>
</ul>
<p><strong>文件描述符</strong>：</p>
<p>使用程序必须在使用前“打开”文件：</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line">f = open(name, flag);</span><br><span class="line"></span><br><span class="line">...=read(f, ...);</span><br><span class="line"></span><br><span class="line">...</span><br><span class="line">close(f);</span><br></pre></td></tr></table></figure>
<p>文件描述符是一个整数，所有打开的文件有一个表，叫做打开文件表，而文件描述符就是打开文件表的索引，当执行read或write操作时，根据索引(文件描述符)查找打开文件表得到相应的文件信息。</p>
<p>操作系统为每个进程维护一个打开文件表。</p>
<p>需要元数据来管理打开文件：</p>
<ul>
<li>文件指针：指向最近的一次读写位置，每个打开了这个文件的进程都有这个指针</li>
<li>文件打开计数：记录文件打开的次数，当最后一个进程关闭了文件时，允许将其从打开文件表中移除</li>
<li>文件磁盘位置：缓存数据访问信息</li>
<li>访问权限：每个程序访问模式信息</li>
</ul>
<p>操作系统内部视角：</p>
<ul>
<li>块的集合（块时逻辑转换单元，而扇区是物理转换单元）</li>
<li>块大小 &lt;&gt; 扇区大小</li>
</ul>
<p>多用户文件中的文件共享很必要的。</p>
<ul>
<li>访问控制：</li>
<li>文件访问控制列表(ACL)</li>
<li>Unix模式<ul>
<li>用户ID识别用户，表明每个用户所允许的权限及保护模式</li>
<li>组ID允许用户组成组，并指定了组访问权限</li>
</ul>
</li>
</ul>
<p><strong>目录</strong>：文件以目录的方式组织起来</p>
<p>目录是一类特殊的文件，每个目录包含了一张表。</p>
<p>目录的操作：</p>
<ul>
<li>搜索文件</li>
<li>创建文件</li>
<li>删除文件</li>
<li>枚举文件</li>
<li>重命名</li>
<li>….</li>
</ul>
<p>一个文件系统需要先挂载才能被访问。</p>
<p>一个未挂载的文件系统被挂载在挂载点上。</p>
<p><strong>文件别名</strong>：</p>
<p>两个或多个文件名关联同一个文件。</p>
<p>硬链接：多个文件项指向一个文件，</p>
<p>软链接：以“快捷方式”指向其他文件，文件中存储的另一个文件的路径</p>
<p>通过存储真实文件的逻辑名称来实现。</p>
<p>如果删除一个有别名的文件会如何呢？</p>
<p>软链接：这个别名将成为一个“悬空指针”。</p>
<p>硬链接：文件块信息中有一个别名计数，只有当所有硬链接被删除了，才会删除文件</p>
<p>引入链接机制，如何保证没有循环？</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191111153514.png" alt=""></p>
<ul>
<li>通过循环检测算法</li>
<li>限制路径可遍历文件目录的数量</li>
</ul>
<p><strong>文件系统种类</strong>：</p>
<ul>
<li><p>磁盘文件系统：</p>
<p>文件存储在存储设备上，如磁盘</p>
<p>FAT、NTFS、ext2/3，ISO9660</p>
</li>
<li><p>数据库文件系统：</p>
<p>文件根据其特征可被寻址的</p>
<p>例如WinFs</p>
</li>
<li><p>日志文件系统</p>
<p>记录文件系统的修改/事件</p>
</li>
<li><p>网络/分布式文件系统</p>
<p>NFS、SMB、AFS、GFS</p>
</li>
<li><p>特殊/虚拟文件系统</p>
<p>不是为了存储数据，而是给读和写一种接口</p>
</li>
</ul>
<h2 id="虚拟文件系统"><a href="#虚拟文件系统" class="headerlink" title="虚拟文件系统"></a>虚拟文件系统</h2><p>分层结构：</p>
<ul>
<li>上层：虚拟文件系统</li>
<li>底层：特定文件系统模块</li>
</ul>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191112092911.png" alt=""></p>
<p>目的：对所有不同文件系统的抽象</p>
<p>功能：</p>
<ul>
<li>提供相同的文件和文件系统接口</li>
<li>高效查询例程，遍历文件系统</li>
<li>与特定文件系统模块的交互</li>
</ul>
<p>卷控制块：(Unix: “Superblock”)</p>
<ul>
<li>每个文件系统有一个</li>
<li>文件系统详细信息</li>
<li>块，块大小，空闲块，计数/指针等</li>
</ul>
<p>文件控制块：（Unix: “vnode”or”inode”）</p>
<ul>
<li>每个文件一个</li>
<li>文件详细信息</li>
<li>许可，拥有者，大小，数据库位置等</li>
</ul>
<p>目录结点（Linux：“dentry”）</p>
<ul>
<li>每个目录项一个（目录和文件）</li>
<li>将目录项数据结构及树型布局编码成树型数据结构</li>
<li>指向文件控制块，父节点，项目列表等</li>
</ul>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191112093431.png" alt=""></p>
<p>文件系统数据结构：</p>
<ul>
<li>卷控制块</li>
<li>文件控制块</li>
<li>目录结点</li>
</ul>
<p>当需要时加进内存：</p>
<ul>
<li>卷控制模块：当文件系统挂载时进入内存</li>
<li>文件控制块：当文件被访问时进入内存</li>
<li>目录结点：在遍历一个文件路径时进入内存</li>
</ul>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191112093704.png" alt=""></p>
<h2 id="数据缓冲"><a href="#数据缓冲" class="headerlink" title="数据缓冲"></a>数据缓冲</h2><p>![](<a href="https://raw.githubusercontent.com/zxpgo/images/master/img/20191112093928.png" target="_blank" rel="noopener">https://raw.githubusercontent.com/zxpgo/images/master/img/20191112093928.png</a></p>
<p>基于页的缓冲，方便应用程序读取。</p>
<h2 id="打开文件的数据结构"><a href="#打开文件的数据结构" class="headerlink" title="打开文件的数据结构"></a>打开文件的数据结构</h2><p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191112095442.png" alt=""></p>
<p>根据打开文件表中的文件信息，找到文件在磁盘中的扇区，然后读取扇区中的数据。</p>
<h2 id="文件分配"><a href="#文件分配" class="headerlink" title="文件分配"></a>文件分配</h2><p>分配方式：</p>
<ul>
<li>连续分配</li>
<li>链式分配</li>
<li>索引分配</li>
</ul>
<p><strong>连续分配：</strong></p>
<p>分配策略：最先匹配、最佳匹配、最差匹配</p>
<p>优势：文件读取表现好，高效的顺序和随机访问</p>
<p>缺点：碎片，文件增长问题</p>
<p><strong>链式分配</strong></p>
<p>文件以数据块链表方式存储</p>
<p>优点：创建、增大、缩小很容易；没有碎片</p>
<p>缺点：不可能进行真正的随机访问，可靠性</p>
<p><strong>索引分配</strong></p>
<p>为每个文件创建一个名为索引数据块的非数据数据块</p>
<p>优点: 创建、增大、缩小容易；没有碎片；支持直接访问</p>
<p>缺点：当文件很小时，存储索引的开销；索引块大小有限，如果存储大文件呢？</p>
<p>对于大文件的解决方案：</p>
<p>链式索引块和多级索引块：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191112101137.png" alt=""></p>
<p>多级索引块和多级页表有相同之处。</p>
<p>Unix早期三级文件索引：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191112101335.png" alt=""></p>
<h2 id="空间空间列表"><a href="#空间空间列表" class="headerlink" title="空间空间列表"></a>空间空间列表</h2><p>用位图代表空闲数据块列表：</p>
<p>11111110000001111111111000101</p>
<p>如果$i=0$表明数据块$i$是空闲的，反之则已分配。</p>
<p>位图存储在磁盘中，需要读取到内存中来。需要确保两者的一致性。解决方案：</p>
<ul>
<li>现在磁盘上设置对应的位bit[i]=1</li>
<li>分配block[i]</li>
<li>在内存中设置bit[i]=1</li>
</ul>
<p>即使在磁盘中设置bit[i]=1，然后掉电了没有将数据写入，也不会有数据丢失的情况。</p>
<p>链式列表和分组列表：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191112102213.png" alt=""></p>
<h2 id="多磁盘管理-RAID"><a href="#多磁盘管理-RAID" class="headerlink" title="多磁盘管理-RAID"></a>多磁盘管理-RAID</h2><p>磁盘是一个机械设备。下面是基本的原理图：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191112102405.png" alt=""></p>
<p>分区：硬件磁盘的一种适合操作系统指定格式的划分</p>
<p>卷：一个拥有一个文件系统实例的可访问的存储空间</p>
<p>RAID:冗余磁盘阵列</p>
<p>不同RAID分类：RAID-0,RAID-1,RAID-5</p>
<p><strong>RAID0:</strong></p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191112105956.png" alt=""></p>
<p>提高了访问速度。数据存储到不同的盘，提高访问速度。</p>
<p><strong>RAID1:</strong></p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191112110015.png" alt=""></p>
<p>提高了可靠性。存储一个相同的备份。</p>
<p><strong>RAID4:</strong></p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191112105646.png" alt=""></p>
<p>添加一个额外的盘来支持容错，但是只能在一个盘坏了的情况下才能恢复。结合了RAID-0和RAID-1的特性。往Disk i写数据时，Parity Disk也要进行写数据，这样Parity Disk写数据变成了瓶颈。</p>
<p><strong>RAID-5:</strong></p>
<p>将RAID-4中Parity Disk的开销分到每个Disk中，就得到了RAID-5。</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20191112105812.png" alt=""></p>
<p>校验的开销是均匀的。保证了高可靠性，但是只能矫正一个磁盘的错误。</p>
<p>需要矫正两个盘的错误，需要采用RAID-6等。</p>
<p>RAID-0/4/5：基于快级别的校验</p>
<p>RAID-3：基于bit级别的校验</p>
<p>RAID-5是最常用的。</p>
<h2 id="磁盘调度"><a href="#磁盘调度" class="headerlink" title="磁盘调度"></a>磁盘调度</h2><p>磁盘可以有多个盘片，每个盘片有一个或两个磁头，（两个磁头对应正反面）。</p>
<p>磁头的旋转和前后移动，都是机械操作，速度非常慢。</p>
<p><strong>寻道时间：</strong>定位到期望的磁道所花费的时间</p>
<p><strong>旋转延迟：</strong>从扇区的开始处到达目的处花费的时间</p>
<p>平均旋转延迟时间=磁盘转换一周时间的一半</p>
<p>访问时间：</p>
<p>寻道时间的开销是最大的。</p>
<p><strong>先进先出：</strong></p>
<p>应用程序访问的磁盘的按照先来先处理的原则。</p>
<p><strong>最短服务优先</strong>：</p>
<p>会出现饥饿现象。</p>
<p><strong>SCAN方法：</strong></p>
<p>磁盘在一个方向移动，满足所有为完成的请求，直到磁盘到达该方向上最后的磁道。</p>
<p><strong>C-SCAN：</strong>限制了仅在一个方向上扫面。到达最后的磁道，直接跳到最前面的磁道重新开始扫描。</p>
<p><strong>C-SCAN改进：</strong>磁臂先到达该方向上最后<strong>最后一个请求处</strong>，然后立即反转。</p>
<p><strong>N-Step-SCAN算法：</strong>将磁盘请求队列分成若干个长度为N的子队列，磁盘调用将按FCFS算法依次处理这些子队列。而每处理一个队列时又是按SCAN算法，对一个队列处理完后，再处理其他队列。</p>

      
    </div>
    
    
    

    
      <div>
        <div id="wechat_subscriber" style="display: block; padding: 10px 0; margin: 20px auto; width: 100%; text-align: center">
    <img id="wechat_subscriber_qcode" src="/images/wechat-qcode.jpg" alt="zxp wechat" style="width: 200px; max-width: 100%;"/>
    <div>欢迎关注微信公众号！</div>
</div>

      </div>
    

    
      <div>
        <div style="padding: 10px 0; margin: 20px auto; width: 90%; text-align: center;">
  <div></div>
  <button id="rewardButton" disable="enable" onclick="var qr = document.getElementById('QR'); if (qr.style.display === 'none') {qr.style.display='block';} else {qr.style.display='none'}">
    <span>打赏</span>
  </button>
  <div id="QR" style="display: none;">

    
      <div id="wechat" style="display: inline-block">
        <img id="wechat_qr" src="/images/WeChatpay.jpg" alt="zxp 微信支付"/>
        <p>微信支付</p>
      </div>
    

    
      <div id="alipay" style="display: inline-block">
        <img id="alipay_qr" src="/images/Alipay.jpg" alt="zxp 支付宝"/>
        <p>支付宝</p>
      </div>
    

    

  </div>
</div>

      </div>
    

    
      <div>
        <ul class="post-copyright">
  <li class="post-copyright-author">
    <strong>本文作者：</strong>
    zxp
  </li>
  <li class="post-copyright-link">
    <strong>本文链接：</strong>
    <a href="https://zxpgo.github.io/2019/11/04/操作系统复习/" title="操作系统学习笔记">https://zxpgo.github.io/2019/11/04/操作系统复习/</a>
  </li>
  <li class="post-copyright-license">
    <strong>版权声明： </strong>
    本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-nc-sa/3.0/" rel="external nofollow" target="_blank">CC BY-NC-SA 3.0</a> 许可协议。转载请注明出处！
  </li>
</ul>

      </div>
    

    <footer class="post-footer">
      
        <div class="post-tags">
          
            <a href="/tag/操作系统/" rel="tag"># 操作系统</a>
          
        </div>
      

      
      
        <div class="post-widgets">
        

        

        
          
          <div id="needsharebutton-postbottom">
            <span class="btn">
              <i class="fa fa-share-alt" aria-hidden="true"></i>
            </span>
          </div>
        
        </div>
      
      

      
        <div class="post-nav">
          <div class="post-nav-next post-nav-item">
            
              <a href="/2019/11/01/剑指offer之面试中的各项能力/" rel="next" title="剑指offer-面试中的各项能力">
                <i class="fa fa-chevron-left"></i> 剑指offer-面试中的各项能力
              </a>
            
          </div>

          <span class="post-nav-divider"></span>

          <div class="post-nav-prev post-nav-item">
            
              <a href="/2019/11/18/云盘项目/" rel="prev" title="图床项目笔记">
                图床项目笔记 <i class="fa fa-chevron-right"></i>
              </a>
            
          </div>
        </div>
      

      
      
    </footer>
  </div>
  
  
  
  </article>



    <div class="post-spread">
      
    </div>
  </div>


          </div>
          


          

  
    <div class="comments" id="comments">
      <div id="lv-container" data-id="city" data-uid="MTAyMC8zODgxNC8xNTM0Mg=="></div>
    </div>

  



        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    
    <div class="sidebar-inner">

      

      
        <ul class="sidebar-nav motion-element">
          <li class="sidebar-nav-toc sidebar-nav-active" data-target="post-toc-wrap">
            文章目录
          </li>
          <li class="sidebar-nav-overview" data-target="site-overview-wrap">
            站点概览
          </li>
        </ul>
      

      <section class="site-overview-wrap sidebar-panel">
        <div class="site-overview">
          <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
            
              <img class="site-author-image" itemprop="image"
                src="/images/avatar.gif"
                alt="zxp" />
            
              <p class="site-author-name" itemprop="name">zxp</p>
              <p class="site-description motion-element" itemprop="description"></p>
          </div>

          <nav class="site-state motion-element">

            
              <div class="site-state-item site-state-posts">
              
                <a href="/archives/">
              
                  <span class="site-state-item-count">176</span>
                  <span class="site-state-item-name">日志</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-categories">
                <a href="/categories/index.html">
                  <span class="site-state-item-count">16</span>
                  <span class="site-state-item-name">分类</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-tags">
                <a href="/tags/index.html">
                  <span class="site-state-item-count">48</span>
                  <span class="site-state-item-name">标签</span>
                </a>
              </div>
            

          </nav>

          
            <div class="feed-link motion-element">
              <a href="/atom.xml" rel="alternate">
                <i class="fa fa-rss"></i>
                RSS
              </a>
            </div>
          

          
            <div class="links-of-author motion-element">
                
                  <span class="links-of-author-item">
                    <a href="https://blog.csdn.net/qq_25774883" target="_blank" title="CSDN">
                      
                        <i class="fa fa-fw fa-globe"></i>CSDN</a>
                  </span>
                
                  <span class="links-of-author-item">
                    <a href="https://github.com/zxpgo/zxpgo" target="_blank" title="GitHub">
                      
                        <i class="fa fa-fw fa-globe"></i>GitHub</a>
                  </span>
                
                  <span class="links-of-author-item">
                    <a href="https://www.linkedin.com/feed/" target="_blank" title="LinkedIn">
                      
                        <i class="fa fa-fw fa-globe"></i>LinkedIn</a>
                  </span>
                
                  <span class="links-of-author-item">
                    <a href="1165772354@qq.com" target="_blank" title="E-Mail">
                      
                        <i class="fa fa-fw fa-envelope"></i>E-Mail</a>
                  </span>
                
            </div>
          

          
          

          
          
            <div class="links-of-blogroll motion-element links-of-blogroll-inline">
              <div class="links-of-blogroll-title">
                <i class="fa  fa-fw fa-link"></i>
                友情链接
              </div>
              <ul class="links-of-blogroll-list">
                
                  <li class="links-of-blogroll-item">
                    <a href="http://theme-next.iissnan.com" title="Next主题" target="_blank">Next主题</a>
                  </li>
                
                  <li class="links-of-blogroll-item">
                    <a href="http://blog.rexking6.top" title="青爷博客" target="_blank">青爷博客</a>
                  </li>
                
                  <li class="links-of-blogroll-item">
                    <a href="https://me.csdn.net/download/qq_25774883" title="CSDN下载" target="_blank">CSDN下载</a>
                  </li>
                
                  <li class="links-of-blogroll-item">
                    <a href="https://www.livere.com/" title="来必力" target="_blank">来必力</a>
                  </li>
                
                  <li class="links-of-blogroll-item">
                    <a href="https://tongji.baidu.com/web/welcome/login" title="百度统计" target="_blank">百度统计</a>
                  </li>
                
                  <li class="links-of-blogroll-item">
                    <a href="https://leancloud.cn/" title="LeanCloud" target="_blank">LeanCloud</a>
                  </li>
                
                  <li class="links-of-blogroll-item">
                    <a href="http://ibruce.info/2015/04/04/busuanzi/" title="不蒜子" target="_blank">不蒜子</a>
                  </li>
                
                  <li class="links-of-blogroll-item">
                    <a href="https://leetcode-cn.com/" title="LeetCode" target="_blank">LeetCode</a>
                  </li>
                
              </ul>
            </div>
          

          

        </div>
      </section>

      
      <!--noindex-->
        <section class="post-toc-wrap motion-element sidebar-panel sidebar-panel-active">
          <div class="post-toc">

            
              
            

            
              <div class="post-toc-content"><ol class="nav"><li class="nav-item nav-level-2"><a class="nav-link" href="#操作系统启动"><span class="nav-number">1.</span> <span class="nav-text">操作系统启动</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#中断、异常和系统调用"><span class="nav-number">2.</span> <span class="nav-text">中断、异常和系统调用</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#定义"><span class="nav-number">2.1.</span> <span class="nav-text">定义</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#中断"><span class="nav-number">2.2.</span> <span class="nav-text">中断</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#异常"><span class="nav-number">2.3.</span> <span class="nav-text">异常</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#系统调用"><span class="nav-number">2.4.</span> <span class="nav-text">系统调用</span></a></li></ol></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#内存"><span class="nav-number"></span> <span class="nav-text">内存</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#计算机体系结构及内存分层体系"><span class="nav-number">1.</span> <span class="nav-text">计算机体系结构及内存分层体系</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#计算机体系结构-内存分层体系"><span class="nav-number">1.1.</span> <span class="nav-text">计算机体系结构/内存分层体系</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#地址空间和地址生成"><span class="nav-number">1.2.</span> <span class="nav-text">地址空间和地址生成</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#逻辑地址生成"><span class="nav-number">1.2.1.</span> <span class="nav-text">逻辑地址生成</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#连续内存分配"><span class="nav-number">1.3.</span> <span class="nav-text">连续内存分配</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#分配策略"><span class="nav-number">1.3.1.</span> <span class="nav-text">分配策略</span></a><ol class="nav-child"><li class="nav-item nav-level-5"><a class="nav-link" href="#首次适配"><span class="nav-number">1.3.1.1.</span> <span class="nav-text">首次适配</span></a></li><li class="nav-item nav-level-5"><a class="nav-link" href="#最佳适配"><span class="nav-number">1.3.1.2.</span> <span class="nav-text">最佳适配</span></a></li><li class="nav-item nav-level-5"><a class="nav-link" href="#最差适配"><span class="nav-number">1.3.1.3.</span> <span class="nav-text">最差适配</span></a></li></ol></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#压缩式碎片整理"><span class="nav-number">1.4.</span> <span class="nav-text">压缩式碎片整理</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#交换式碎片整理"><span class="nav-number">1.5.</span> <span class="nav-text">交换式碎片整理</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#非连续内存分配"><span class="nav-number">2.</span> <span class="nav-text">非连续内存分配</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#分段"><span class="nav-number">2.1.</span> <span class="nav-text">分段</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#程序的分段地址空间"><span class="nav-number">2.1.1.</span> <span class="nav-text">程序的分段地址空间</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#分段寻址方案"><span class="nav-number">2.1.2.</span> <span class="nav-text">分段寻址方案</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#分页"><span class="nav-number">2.2.</span> <span class="nav-text">分页</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#分页地址空间"><span class="nav-number">2.2.1.</span> <span class="nav-text">分页地址空间</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#页寻址方案"><span class="nav-number">2.2.2.</span> <span class="nav-text">页寻址方案</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#页表"><span class="nav-number">2.3.</span> <span class="nav-text">页表</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#分页机制的问题"><span class="nav-number">2.3.1.</span> <span class="nav-text">分页机制的问题</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#Translation-Look-aside-Bufer-TLB"><span class="nav-number">2.3.2.</span> <span class="nav-text">Translation Look-aside Bufer(TLB)</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#二级页表"><span class="nav-number">2.3.3.</span> <span class="nav-text">二级页表</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#多级页表"><span class="nav-number">2.3.4.</span> <span class="nav-text">多级页表</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#反向页表"><span class="nav-number">2.3.5.</span> <span class="nav-text">反向页表</span></a><ol class="nav-child"><li class="nav-item nav-level-5"><a class="nav-link" href="#基于页寄存器的方案"><span class="nav-number">2.3.5.1.</span> <span class="nav-text">基于页寄存器的方案</span></a></li><li class="nav-item nav-level-5"><a class="nav-link" href="#基于关联内存的方案"><span class="nav-number">2.3.5.2.</span> <span class="nav-text">基于关联内存的方案</span></a></li><li class="nav-item nav-level-5"><a class="nav-link" href="#基于哈希查找的方案"><span class="nav-number">2.3.5.3.</span> <span class="nav-text">基于哈希查找的方案</span></a></li></ol></li></ol></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#虚拟内存"><span class="nav-number">3.</span> <span class="nav-text">虚拟内存</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#虚拟内存起因"><span class="nav-number">3.1.</span> <span class="nav-text">虚拟内存起因</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#覆盖技术"><span class="nav-number">3.2.</span> <span class="nav-text">覆盖技术</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#交换技术"><span class="nav-number">3.3.</span> <span class="nav-text">交换技术</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#虚存技术"><span class="nav-number">3.4.</span> <span class="nav-text">虚存技术</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#虚拟页式内存管理"><span class="nav-number">3.4.1.</span> <span class="nav-text">虚拟页式内存管理</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#虚拟内存性能"><span class="nav-number">3.4.2.</span> <span class="nav-text">虚拟内存性能</span></a></li></ol></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#页面置换算法"><span class="nav-number">4.</span> <span class="nav-text">页面置换算法</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#最优页面置换算法"><span class="nav-number">4.1.</span> <span class="nav-text">最优页面置换算法</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#先进先出算法FIFO"><span class="nav-number">4.2.</span> <span class="nav-text">先进先出算法FIFO</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#最近最久未使用算法（LRU）"><span class="nav-number">4.3.</span> <span class="nav-text">最近最久未使用算法（LRU）</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#时钟页面置换算法"><span class="nav-number">4.4.</span> <span class="nav-text">时钟页面置换算法</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#二次机会"><span class="nav-number">4.5.</span> <span class="nav-text">二次机会</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#最不常用算法LFU"><span class="nav-number">4.6.</span> <span class="nav-text">最不常用算法LFU</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#Belady现象"><span class="nav-number">4.7.</span> <span class="nav-text">Belady现象</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#对于FIFO算法"><span class="nav-number">4.7.1.</span> <span class="nav-text">对于FIFO算法</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#对于LRU"><span class="nav-number">4.7.2.</span> <span class="nav-text">对于LRU</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#LRU、FIFO、Clock算法比较"><span class="nav-number">4.8.</span> <span class="nav-text">LRU、FIFO、Clock算法比较</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#局部页面置换算法的问题、工作集模型"><span class="nav-number">4.9.</span> <span class="nav-text">局部页面置换算法的问题、工作集模型</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#工作集模型"><span class="nav-number">4.9.1.</span> <span class="nav-text">工作集模型</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#常驻集"><span class="nav-number">4.9.2.</span> <span class="nav-text">常驻集</span></a></li></ol></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#两个全局置换算法"><span class="nav-number">5.</span> <span class="nav-text">两个全局置换算法</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#工作集页置换算法"><span class="nav-number">5.1.</span> <span class="nav-text">工作集页置换算法</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#缺页率页面置换算法"><span class="nav-number">5.2.</span> <span class="nav-text">缺页率页面置换算法</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#抖动问题"><span class="nav-number">6.</span> <span class="nav-text">抖动问题</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#进程"><span class="nav-number"></span> <span class="nav-text">进程</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#进程描述-静态"><span class="nav-number">1.</span> <span class="nav-text">进程描述(静态)</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#进程的定义"><span class="nav-number">1.1.</span> <span class="nav-text">进程的定义</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#进程的组成"><span class="nav-number">1.2.</span> <span class="nav-text">进程的组成</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#进程的特点"><span class="nav-number">1.3.</span> <span class="nav-text">进程的特点</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#进程控制结构"><span class="nav-number">1.4.</span> <span class="nav-text">进程控制结构</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#进程状态-动态"><span class="nav-number">2.</span> <span class="nav-text">进程状态(动态)</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#进程的生命周期"><span class="nav-number">2.1.</span> <span class="nav-text">进程的生命周期</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#进程状态变化模型"><span class="nav-number">2.2.</span> <span class="nav-text">进程状态变化模型</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#进程挂起"><span class="nav-number">3.</span> <span class="nav-text">进程挂起</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#线程"><span class="nav-number">4.</span> <span class="nav-text">线程</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#为什么需要线程？"><span class="nav-number">4.1.</span> <span class="nav-text">为什么需要线程？</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#什么是线程？"><span class="nav-number">4.2.</span> <span class="nav-text">什么是线程？</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#线程的实现方式"><span class="nav-number">4.3.</span> <span class="nav-text">线程的实现方式</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#用户线程"><span class="nav-number">4.3.1.</span> <span class="nav-text">用户线程</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#内核线程"><span class="nav-number">4.3.2.</span> <span class="nav-text">内核线程</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#轻量级进程"><span class="nav-number">4.3.3.</span> <span class="nav-text">轻量级进程</span></a></li></ol></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#上下文切换"><span class="nav-number">5.</span> <span class="nav-text">上下文切换</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#创建进程"><span class="nav-number">6.</span> <span class="nav-text">创建进程</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#进程等待和终止"><span class="nav-number">7.</span> <span class="nav-text">进程等待和终止</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#调度算法"><span class="nav-number">8.</span> <span class="nav-text">调度算法</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#调度原则"><span class="nav-number">8.1.</span> <span class="nav-text">调度原则</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#通用计算机调度算法"><span class="nav-number">8.2.</span> <span class="nav-text">通用计算机调度算法</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#FCFS-先来先服务"><span class="nav-number">8.2.1.</span> <span class="nav-text">FCFS(先来先服务)</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#SJF-短作业优先"><span class="nav-number">8.2.2.</span> <span class="nav-text">SJF(短作业优先)</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#HRRN-最高响应比优先"><span class="nav-number">8.2.3.</span> <span class="nav-text">HRRN(最高响应比优先)</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#Round-Robin-轮询"><span class="nav-number">8.2.4.</span> <span class="nav-text">Round Robin(轮询)</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#Multilevel-Feedback-Queues-多级反馈队列"><span class="nav-number">8.2.5.</span> <span class="nav-text">Multilevel Feedback Queues(多级反馈队列)</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#Fair-Share-Scheduling-公平共享调度"><span class="nav-number">8.2.6.</span> <span class="nav-text">Fair Share Scheduling(公平共享调度)</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#总结"><span class="nav-number">8.2.7.</span> <span class="nav-text">总结</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#实时调度"><span class="nav-number">8.3.</span> <span class="nav-text">实时调度</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#RM速度单调调度"><span class="nav-number">8.3.1.</span> <span class="nav-text">RM速度单调调度</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#EDF最早期限调度"><span class="nav-number">8.3.2.</span> <span class="nav-text">EDF最早期限调度</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#多处理器调度"><span class="nav-number">8.4.</span> <span class="nav-text">多处理器调度</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#优先级反转问题"><span class="nav-number">8.5.</span> <span class="nav-text">优先级反转问题</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#同步"><span class="nav-number">9.</span> <span class="nav-text">同步</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#概念"><span class="nav-number">9.1.</span> <span class="nav-text">概念</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#临界区"><span class="nav-number">9.2.</span> <span class="nav-text">临界区</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#禁用硬件中断"><span class="nav-number">9.3.</span> <span class="nav-text">禁用硬件中断</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#基于软件的解决办法"><span class="nav-number">9.4.</span> <span class="nav-text">基于软件的解决办法</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#更高级的抽象"><span class="nav-number">9.5.</span> <span class="nav-text">更高级的抽象</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#信号量"><span class="nav-number">9.6.</span> <span class="nav-text">信号量</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#信号量使用"><span class="nav-number">9.7.</span> <span class="nav-text">信号量使用</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#信号量的实现"><span class="nav-number">9.8.</span> <span class="nav-text">信号量的实现</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#管程"><span class="nav-number">9.9.</span> <span class="nav-text">管程</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#经典同步问题"><span class="nav-number">9.10.</span> <span class="nav-text">经典同步问题</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#读者-写者问题"><span class="nav-number">9.10.1.</span> <span class="nav-text">读者-写者问题</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#哲学家就餐问题"><span class="nav-number">9.10.2.</span> <span class="nav-text">哲学家就餐问题</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#死锁"><span class="nav-number">9.11.</span> <span class="nav-text">死锁</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#死锁特征"><span class="nav-number">9.11.1.</span> <span class="nav-text">死锁特征</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#死锁处理办法"><span class="nav-number">9.11.2.</span> <span class="nav-text">死锁处理办法</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#银行家算法"><span class="nav-number">9.11.3.</span> <span class="nav-text">银行家算法</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#进程间通信-IPC"><span class="nav-number">9.12.</span> <span class="nav-text">进程间通信(IPC)</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#信号"><span class="nav-number">9.12.1.</span> <span class="nav-text">信号</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#管道"><span class="nav-number">9.12.2.</span> <span class="nav-text">管道</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#消息队列"><span class="nav-number">9.12.3.</span> <span class="nav-text">消息队列</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#共享内存"><span class="nav-number">9.12.4.</span> <span class="nav-text">共享内存</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#socket"><span class="nav-number">9.12.5.</span> <span class="nav-text">socket</span></a></li></ol></li></ol></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#文件系统"><span class="nav-number"></span> <span class="nav-text">文件系统</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#基本概念"><span class="nav-number">1.</span> <span class="nav-text">基本概念</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#虚拟文件系统"><span class="nav-number">2.</span> <span class="nav-text">虚拟文件系统</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#数据缓冲"><span class="nav-number">3.</span> <span class="nav-text">数据缓冲</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#打开文件的数据结构"><span class="nav-number">4.</span> <span class="nav-text">打开文件的数据结构</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#文件分配"><span class="nav-number">5.</span> <span class="nav-text">文件分配</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#空间空间列表"><span class="nav-number">6.</span> <span class="nav-text">空间空间列表</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#多磁盘管理-RAID"><span class="nav-number">7.</span> <span class="nav-text">多磁盘管理-RAID</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#磁盘调度"><span class="nav-number">8.</span> <span class="nav-text">磁盘调度</span></a></li></ol></div>
            

          </div>
        </section>
      <!--/noindex-->
      

      

    </div>
  </aside>


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div>
<script async src="https//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
<i class="fa fa-user-md"></i><span id="busuanzi_container_site_pv" style='display:none'>
    本站总访问量 <span id="busuanzi_value_site_pv"></span> 
    <span class="post-meta-divider">|</span>
</span>
<span id="busuanzi_container_site_uv" style='display:none'>
    访问人数 <span id="busuanzi_value_site_uv"></span>
</span>
</div>


<script async src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>

<div class="copyright">&copy; 2018-8 &mdash; <span itemprop="copyrightYear">2020</span>
  <span class="with-love">
    <i class="fa fa-"></i> Power by 
  </span>
  <span class="author" itemprop="copyrightHolder">zxp</span>
  
  
</div>









        







        
      </div>
    </footer>

    
      <div class="back-to-top">
        <i class="fa fa-arrow-up"></i>
        
      </div>
    

    
      <div id="needsharebutton-float">
        <span class="btn">
          <i class="fa fa-share-alt" aria-hidden="true"></i>
        </span>
      </div>
    

  </div>

  

<script type="text/javascript">
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>









  












  
  
    <script type="text/javascript" src="/lib/jquery/index.js?v=2.1.3"></script>
  

  
  
    <script type="text/javascript" src="/lib/fastclick/lib/fastclick.min.js?v=1.0.6"></script>
  

  
  
    <script type="text/javascript" src="/lib/jquery_lazyload/jquery.lazyload.js?v=1.9.7"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/fancybox/source/jquery.fancybox.pack.js?v=2.1.5"></script>
  


  


  <script type="text/javascript" src="/js/src/utils.js?v=5.1.4"></script>

  <script type="text/javascript" src="/js/src/motion.js?v=5.1.4"></script>



  
  


  <script type="text/javascript" src="/js/src/affix.js?v=5.1.4"></script>

  <script type="text/javascript" src="/js/src/schemes/pisces.js?v=5.1.4"></script>



  
  <script type="text/javascript" src="/js/src/scrollspy.js?v=5.1.4"></script>
<script type="text/javascript" src="/js/src/post-details.js?v=5.1.4"></script>



  


  <script type="text/javascript" src="/js/src/bootstrap.js?v=5.1.4"></script>



  


  




	





  




  
  <div id="lv-container" data-uid="MTAyMC8zODgxNC8xNTM0Mg==">
    <script type="text/javascript">
      (function(d, s) {
        var j, e = d.getElementsByTagName(s)[0];
        if (typeof LivereTower === 'function') { return; }
        j = d.createElement(s);
        j.src = 'https://cdn-city.livere.com/js/embed.dist.js';
        j.async = true;
        e.parentNode.insertBefore(j, e);
      })(document, 'script');
    </script>
	</div>
  











  

  <script type="text/javascript">
    // Popup Window;
    var isfetched = false;
    var isXml = true;
    // Search DB path;
    var search_path = "search.xml";
    if (search_path.length === 0) {
      search_path = "search.xml";
    } else if (/json$/i.test(search_path)) {
      isXml = false;
    }
    var path = "/" + search_path;
    // monitor main search box;

    var onPopupClose = function (e) {
      $('.popup').hide();
      $('#local-search-input').val('');
      $('.search-result-list').remove();
      $('#no-result').remove();
      $(".local-search-pop-overlay").remove();
      $('body').css('overflow', '');
    }

    function proceedsearch() {
      $("body")
        .append('<div class="search-popup-overlay local-search-pop-overlay"></div>')
        .css('overflow', 'hidden');
      $('.search-popup-overlay').click(onPopupClose);
      $('.popup').toggle();
      var $localSearchInput = $('#local-search-input');
      $localSearchInput.attr("autocapitalize", "none");
      $localSearchInput.attr("autocorrect", "off");
      $localSearchInput.focus();
    }

    // search function;
    var searchFunc = function(path, search_id, content_id) {
      'use strict';

      // start loading animation
      $("body")
        .append('<div class="search-popup-overlay local-search-pop-overlay">' +
          '<div id="search-loading-icon">' +
          '<i class="fa fa-spinner fa-pulse fa-5x fa-fw"></i>' +
          '</div>' +
          '</div>')
        .css('overflow', 'hidden');
      $("#search-loading-icon").css('margin', '20% auto 0 auto').css('text-align', 'center');

      $.ajax({
        url: path,
        dataType: isXml ? "xml" : "json",
        async: true,
        success: function(res) {
          // get the contents from search data
          isfetched = true;
          $('.popup').detach().appendTo('.header-inner');
          var datas = isXml ? $("entry", res).map(function() {
            return {
              title: $("title", this).text(),
              content: $("content",this).text(),
              url: $("url" , this).text()
            };
          }).get() : res;
          var input = document.getElementById(search_id);
          var resultContent = document.getElementById(content_id);
          var inputEventFunction = function() {
            var searchText = input.value.trim().toLowerCase();
            var keywords = searchText.split(/[\s\-]+/);
            if (keywords.length > 1) {
              keywords.push(searchText);
            }
            var resultItems = [];
            if (searchText.length > 0) {
              // perform local searching
              datas.forEach(function(data) {
                var isMatch = false;
                var hitCount = 0;
                var searchTextCount = 0;
                var title = data.title.trim();
                var titleInLowerCase = title.toLowerCase();
                var content = data.content.trim().replace(/<[^>]+>/g,"");
                var contentInLowerCase = content.toLowerCase();
                var articleUrl = decodeURIComponent(data.url);
                var indexOfTitle = [];
                var indexOfContent = [];
                // only match articles with not empty titles
                if(title != '') {
                  keywords.forEach(function(keyword) {
                    function getIndexByWord(word, text, caseSensitive) {
                      var wordLen = word.length;
                      if (wordLen === 0) {
                        return [];
                      }
                      var startPosition = 0, position = [], index = [];
                      if (!caseSensitive) {
                        text = text.toLowerCase();
                        word = word.toLowerCase();
                      }
                      while ((position = text.indexOf(word, startPosition)) > -1) {
                        index.push({position: position, word: word});
                        startPosition = position + wordLen;
                      }
                      return index;
                    }

                    indexOfTitle = indexOfTitle.concat(getIndexByWord(keyword, titleInLowerCase, false));
                    indexOfContent = indexOfContent.concat(getIndexByWord(keyword, contentInLowerCase, false));
                  });
                  if (indexOfTitle.length > 0 || indexOfContent.length > 0) {
                    isMatch = true;
                    hitCount = indexOfTitle.length + indexOfContent.length;
                  }
                }

                // show search results

                if (isMatch) {
                  // sort index by position of keyword

                  [indexOfTitle, indexOfContent].forEach(function (index) {
                    index.sort(function (itemLeft, itemRight) {
                      if (itemRight.position !== itemLeft.position) {
                        return itemRight.position - itemLeft.position;
                      } else {
                        return itemLeft.word.length - itemRight.word.length;
                      }
                    });
                  });

                  // merge hits into slices

                  function mergeIntoSlice(text, start, end, index) {
                    var item = index[index.length - 1];
                    var position = item.position;
                    var word = item.word;
                    var hits = [];
                    var searchTextCountInSlice = 0;
                    while (position + word.length <= end && index.length != 0) {
                      if (word === searchText) {
                        searchTextCountInSlice++;
                      }
                      hits.push({position: position, length: word.length});
                      var wordEnd = position + word.length;

                      // move to next position of hit

                      index.pop();
                      while (index.length != 0) {
                        item = index[index.length - 1];
                        position = item.position;
                        word = item.word;
                        if (wordEnd > position) {
                          index.pop();
                        } else {
                          break;
                        }
                      }
                    }
                    searchTextCount += searchTextCountInSlice;
                    return {
                      hits: hits,
                      start: start,
                      end: end,
                      searchTextCount: searchTextCountInSlice
                    };
                  }

                  var slicesOfTitle = [];
                  if (indexOfTitle.length != 0) {
                    slicesOfTitle.push(mergeIntoSlice(title, 0, title.length, indexOfTitle));
                  }

                  var slicesOfContent = [];
                  while (indexOfContent.length != 0) {
                    var item = indexOfContent[indexOfContent.length - 1];
                    var position = item.position;
                    var word = item.word;
                    // cut out 100 characters
                    var start = position - 20;
                    var end = position + 80;
                    if(start < 0){
                      start = 0;
                    }
                    if (end < position + word.length) {
                      end = position + word.length;
                    }
                    if(end > content.length){
                      end = content.length;
                    }
                    slicesOfContent.push(mergeIntoSlice(content, start, end, indexOfContent));
                  }

                  // sort slices in content by search text's count and hits' count

                  slicesOfContent.sort(function (sliceLeft, sliceRight) {
                    if (sliceLeft.searchTextCount !== sliceRight.searchTextCount) {
                      return sliceRight.searchTextCount - sliceLeft.searchTextCount;
                    } else if (sliceLeft.hits.length !== sliceRight.hits.length) {
                      return sliceRight.hits.length - sliceLeft.hits.length;
                    } else {
                      return sliceLeft.start - sliceRight.start;
                    }
                  });

                  // select top N slices in content

                  var upperBound = parseInt('1');
                  if (upperBound >= 0) {
                    slicesOfContent = slicesOfContent.slice(0, upperBound);
                  }

                  // highlight title and content

                  function highlightKeyword(text, slice) {
                    var result = '';
                    var prevEnd = slice.start;
                    slice.hits.forEach(function (hit) {
                      result += text.substring(prevEnd, hit.position);
                      var end = hit.position + hit.length;
                      result += '<b class="search-keyword">' + text.substring(hit.position, end) + '</b>';
                      prevEnd = end;
                    });
                    result += text.substring(prevEnd, slice.end);
                    return result;
                  }

                  var resultItem = '';

                  if (slicesOfTitle.length != 0) {
                    resultItem += "<li><a href='" + articleUrl + "' class='search-result-title'>" + highlightKeyword(title, slicesOfTitle[0]) + "</a>";
                  } else {
                    resultItem += "<li><a href='" + articleUrl + "' class='search-result-title'>" + title + "</a>";
                  }

                  slicesOfContent.forEach(function (slice) {
                    resultItem += "<a href='" + articleUrl + "'>" +
                      "<p class=\"search-result\">" + highlightKeyword(content, slice) +
                      "...</p>" + "</a>";
                  });

                  resultItem += "</li>";
                  resultItems.push({
                    item: resultItem,
                    searchTextCount: searchTextCount,
                    hitCount: hitCount,
                    id: resultItems.length
                  });
                }
              })
            };
            if (keywords.length === 1 && keywords[0] === "") {
              resultContent.innerHTML = '<div id="no-result"><i class="fa fa-search fa-5x" /></div>'
            } else if (resultItems.length === 0) {
              resultContent.innerHTML = '<div id="no-result"><i class="fa fa-frown-o fa-5x" /></div>'
            } else {
              resultItems.sort(function (resultLeft, resultRight) {
                if (resultLeft.searchTextCount !== resultRight.searchTextCount) {
                  return resultRight.searchTextCount - resultLeft.searchTextCount;
                } else if (resultLeft.hitCount !== resultRight.hitCount) {
                  return resultRight.hitCount - resultLeft.hitCount;
                } else {
                  return resultRight.id - resultLeft.id;
                }
              });
              var searchResultList = '<ul class=\"search-result-list\">';
              resultItems.forEach(function (result) {
                searchResultList += result.item;
              })
              searchResultList += "</ul>";
              resultContent.innerHTML = searchResultList;
            }
          }

          if ('auto' === 'auto') {
            input.addEventListener('input', inputEventFunction);
          } else {
            $('.search-icon').click(inputEventFunction);
            input.addEventListener('keypress', function (event) {
              if (event.keyCode === 13) {
                inputEventFunction();
              }
            });
          }

          // remove loading animation
          $(".local-search-pop-overlay").remove();
          $('body').css('overflow', '');

          proceedsearch();
        }
      });
    }

    // handle and trigger popup window;
    $('.popup-trigger').click(function(e) {
      e.stopPropagation();
      if (isfetched === false) {
        searchFunc(path, 'local-search-input', 'local-search-result');
      } else {
        proceedsearch();
      };
    });

    $('.popup-btn-close').click(onPopupClose);
    $('.popup').click(function(e){
      e.stopPropagation();
    });
    $(document).on('keyup', function (event) {
      var shouldDismissSearchPopup = event.which === 27 &&
        $('.search-popup').is(':visible');
      if (shouldDismissSearchPopup) {
        onPopupClose();
      }
    });
  </script>





  

  
  <script src="https://cdn1.lncld.net/static/js/av-core-mini-0.6.4.js"></script>
  <script>AV.initialize("2AyV3DKioBSdoryrFLRohzjB-gzGzoHsz", "XynedcHyJCVCrTfbD4yYnodo");</script>
  <script>
    function showTime(Counter) {
      var query = new AV.Query(Counter);
      var entries = [];
      var $visitors = $(".leancloud_visitors");

      $visitors.each(function () {
        entries.push( $(this).attr("id").trim() );
      });

      query.containedIn('url', entries);
      query.find()
        .done(function (results) {
          var COUNT_CONTAINER_REF = '.leancloud-visitors-count';

          if (results.length === 0) {
            $visitors.find(COUNT_CONTAINER_REF).text(0);
            return;
          }

          for (var i = 0; i < results.length; i++) {
            var item = results[i];
            var url = item.get('url');
            var time = item.get('time');
            var element = document.getElementById(url);

            $(element).find(COUNT_CONTAINER_REF).text(time);
          }
          for(var i = 0; i < entries.length; i++) {
            var url = entries[i];
            var element = document.getElementById(url);
            var countSpan = $(element).find(COUNT_CONTAINER_REF);
            if( countSpan.text() == '') {
              countSpan.text(0);
            }
          }
        })
        .fail(function (object, error) {
          console.log("Error: " + error.code + " " + error.message);
        });
    }

    function addCount(Counter) {
      var $visitors = $(".leancloud_visitors");
      var url = $visitors.attr('id').trim();
      var title = $visitors.attr('data-flag-title').trim();
      var query = new AV.Query(Counter);

      query.equalTo("url", url);
      query.find({
        success: function(results) {
          if (results.length > 0) {
            var counter = results[0];
            counter.fetchWhenSave(true);
            counter.increment("time");
            counter.save(null, {
              success: function(counter) {
                var $element = $(document.getElementById(url));
                $element.find('.leancloud-visitors-count').text(counter.get('time'));
              },
              error: function(counter, error) {
                console.log('Failed to save Visitor num, with error message: ' + error.message);
              }
            });
          } else {
            var newcounter = new Counter();
            /* Set ACL */
            var acl = new AV.ACL();
            acl.setPublicReadAccess(true);
            acl.setPublicWriteAccess(true);
            newcounter.setACL(acl);
            /* End Set ACL */
            newcounter.set("title", title);
            newcounter.set("url", url);
            newcounter.set("time", 1);
            newcounter.save(null, {
              success: function(newcounter) {
                var $element = $(document.getElementById(url));
                $element.find('.leancloud-visitors-count').text(newcounter.get('time'));
              },
              error: function(newcounter, error) {
                console.log('Failed to create');
              }
            });
          }
        },
        error: function(error) {
          console.log('Error:' + error.code + " " + error.message);
        }
      });
    }

    $(function() {
      var Counter = AV.Object.extend("Counter");
      if ($('.leancloud_visitors').length == 1) {
        addCount(Counter);
      } else if ($('.post-title-link').length > 1) {
        showTime(Counter);
      }
    });
  </script>



  

  
<script>
(function(){
    var bp = document.createElement('script');
    var curProtocol = window.location.protocol.split(':')[0];
    if (curProtocol === 'https') {
        bp.src = 'https://zz.bdstatic.com/linksubmit/push.js';        
    }
    else {
        bp.src = 'http://push.zhanzhang.baidu.com/push.js';
    }
    var s = document.getElementsByTagName("script")[0];
    s.parentNode.insertBefore(bp, s);
})();
</script>


  
  
  
  <link rel="stylesheet" href="/lib/needsharebutton/needsharebutton.css">

  
  
  <script src="/lib/needsharebutton/needsharebutton.js"></script>

  <script>
    
      pbOptions = {};
      
          pbOptions.iconStyle = "default";
      
          pbOptions.boxForm = "vertical";
      
          pbOptions.position = "top";
      
          pbOptions.networks = "Weibo,Wechat,Douban,QQZone,Twitter,Facebook";
      
      new needShareButton('#needsharebutton-postbottom', pbOptions);
    
    
      flOptions = {};
      
          flOptions.iconStyle = "box";
      
          flOptions.boxForm = "horizontal";
      
          flOptions.position = "middleRight";
      
          flOptions.networks = "Weibo,Wechat,Douban,QQZone,Twitter,Facebook";
      
      new needShareButton('#needsharebutton-float', flOptions);
    
  </script>

  

  
  
    <script type="text/x-mathjax-config">
      MathJax.Hub.Config({
        tex2jax: {
          inlineMath: [ ['$','$'], ["\\(","\\)"]  ],
          processEscapes: true,
          skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
        }
      });
    </script>

    <script type="text/x-mathjax-config">
      MathJax.Hub.Queue(function() {
        var all = MathJax.Hub.getAllJax(), i;
        for (i=0; i < all.length; i += 1) {
          all[i].SourceElement().parentNode.className += ' has-jax';
        }
      });
    </script>
    <script type="text/javascript" src="//cdn.bootcss.com/mathjax/2.7.1/latest.js?config=TeX-AMS-MML_HTMLorMML"></script>
  


  
  <script type="text/javascript" src="/js/src/js.cookie.js?v=5.1.4"></script>
  <script type="text/javascript" src="/js/src/scroll-cookie.js?v=5.1.4"></script>


  
  <script type="text/javascript" src="/js/src/exturl.js?v=5.1.4"></script>


  
  
  	 <!-- custom analytics part create by xiamo -->
<script src="https://cdn1.lncld.net/static/js/av-core-mini-0.6.1.js"></script>
<script>AV.initialize("2AyV3DKioBSdoryrFLRohzjB-gzGzoHsz", "XynedcHyJCVCrTfbD4yYnodo");</script>
<script>
function showTime(Counter) {
	var query = new AV.Query(Counter);
	$(".leancloud_visitors").each(function() {
		var url = $(this).attr("id").trim();
		query.equalTo("url", url);
		query.find({
			success: function(results) {
				if (results.length == 0) {
					var content = $(document.getElementById(url)).text() + ' 0';
					$(document.getElementById(url)).text(content);
					return;
				}
				for (var i = 0; i < results.length; i++) {
					var object = results[i];
					var content = $(document.getElementById(url)).text() + ' ' + object.get('time');
					$(document.getElementById(url)).text(content);
				}
			}
		});

	});
}

</script>
  
</body>
</html>
